<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta property="og:type" content="website">
<meta property="og:title" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:url" content="http://example.com/page/3/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="StarsWhisper">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main">
  
    <article id="post-【01背包DP练习】洛谷 P1048采药 P1060开心的金明 P1855榨取kkksc03" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%9001%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1048%E9%87%87%E8%8D%AF%20P1060%E5%BC%80%E5%BF%83%E7%9A%84%E9%87%91%E6%98%8E%20P1855%E6%A6%A8%E5%8F%96kkksc03/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%9001%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1048%E9%87%87%E8%8D%AF%20P1060%E5%BC%80%E5%BF%83%E7%9A%84%E9%87%91%E6%98%8E%20P1855%E6%A6%A8%E5%8F%96kkksc03/">【01背包DP练习】洛谷 P1048采药 P1060开心的金明 P1855榨取kkksc03.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p1048采药"><a class="markdownIt-Anchor" href="#洛谷-p1048采药"></a> 洛谷 P1048采药</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1048">https://www.luogu.com.cn/problem/P1048</a></p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span> ,<span class="type">int</span>&gt; PP;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">105</span>;</span><br><span class="line"><span class="type">int</span> tm[N],va[N],dp[<span class="number">1005</span>];</span><br><span class="line"><span class="type">int</span> tt,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   std::cin &gt;&gt; tt &gt;&gt; m;</span><br><span class="line">   <span class="built_in">memset</span>(dp,<span class="number">0</span>,<span class="built_in">sizeof</span>(dp));</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=m; i++) std::cin &gt;&gt; tm[i] &gt;&gt; va[i];</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=m; i++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=tt; j&gt;=tm[i]; j--)&#123;</span><br><span class="line">         dp[j] = std::<span class="built_in">max</span>(dp[j],dp[j-tm[i]]+va[i]);</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   std::cout &lt;&lt; dp[tt];</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​<br />
​</p>
<h2 id="洛谷-p1060-开心的金明"><a class="markdownIt-Anchor" href="#洛谷-p1060-开心的金明"></a> 洛谷 P1060 开心的金明</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1060">https://www.luogu.com.cn/problem/P1060</a></p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span> ,<span class="type">int</span>&gt; PP;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">105</span>,M = <span class="number">30005</span>;</span><br><span class="line"><span class="type">int</span> va[N],we[N],dp[M];</span><br><span class="line"><span class="type">int</span> tt,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   std::cin &gt;&gt; tt &gt;&gt; m;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      std::cin &gt;&gt; va[i] &gt;&gt; we[i];</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=tt; j&gt;=va[i]; j--)&#123;</span><br><span class="line">         dp[j] = std::<span class="built_in">max</span>(dp[j], dp[j-va[i]]+va[i]*we[i]);</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   std::cout &lt;&lt; dp[tt];</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<h2 id="洛谷-p1855-榨取kkksc03"><a class="markdownIt-Anchor" href="#洛谷-p1855-榨取kkksc03"></a> 洛谷 P1855 榨取kkksc03</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1855">https://www.luogu.com.cn/problem/P1855</a><br />
有两样限制的01背包，思路不变</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span> ,<span class="type">int</span>&gt; PP;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">205</span>,M = <span class="number">105</span>;</span><br><span class="line"><span class="type">int</span> dp[N][N];</span><br><span class="line"><span class="type">int</span> mo[M],tm[M];</span><br><span class="line"><span class="type">int</span> n,m,t;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;n,&amp;m,&amp;t);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++)&#123;</span><br><span class="line">      <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;mo[i],&amp;tm[i]);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=m; j&gt;=mo[i]; j--)&#123;</span><br><span class="line">         <span class="keyword">for</span>(<span class="type">int</span> k=t; k&gt;=tm[i]; k--)&#123;</span><br><span class="line">            dp[j][k] = std::<span class="built_in">max</span>(dp[j][k],dp[j-mo[i]][k-tm[i]]+<span class="number">1</span>);</span><br><span class="line">         &#125;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,dp[m][t]);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%9001%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1048%E9%87%87%E8%8D%AF%20P1060%E5%BC%80%E5%BF%83%E7%9A%84%E9%87%91%E6%98%8E%20P1855%E6%A6%A8%E5%8F%96kkksc03/" data-id="cl2uhoebt000ye4j35jcq9z6l" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【AC自动机 _ trie树】G - Word Puzzles   POJ - 1204" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90AC%E8%87%AA%E5%8A%A8%E6%9C%BA%20_%20trie%E6%A0%91%E3%80%91G%20-%20Word%20Puzzles%20%20%20POJ%20-%201204/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90AC%E8%87%AA%E5%8A%A8%E6%9C%BA%20_%20trie%E6%A0%91%E3%80%91G%20-%20Word%20Puzzles%20%20%20POJ%20-%201204/">【AC自动机 _ trie树】G - Word Puzzles   POJ - 1204.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%AD%97%E7%AC%A6%E4%B8%B2/">字符串</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>Word puzzles are usually simple and very entertaining for all ages. They are<br />
so entertaining that Pizza-Hut company started using table covers with word<br />
puzzles printed on them, possibly with the intent to minimise their client’s<br />
perception of any possible delay in bringing them their order.</p>
<p>Even though word puzzles may be entertaining to solve by hand, they may become<br />
boring when they get very large. Computers do not yet get bored in solving<br />
tasks, therefore we thought you could devise a program to speedup (hopefully!)<br />
solution finding in such puzzles.</p>
<p>The following figure illustrates the PizzaHut puzzle. The names of the pizzas<br />
to be found in the puzzle are: MARGARITA, ALEMA, BARBECUE, TROPICAL, SUPREMA,<br />
LOUISIANA, CHEESEHAM, EUROPA, HAVAIANA,<br />
CAMPONESA.![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuL2QwYzAxMDE5MTcwNDBkMTY2NTgzYmE5YzNhYWQ4Yzkz?x-oss-">https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuL2QwYzAxMDE5MTcwNDBkMTY2NTgzYmE5YzNhYWQ4Yzkz?x-oss-</a><br />
process=image/format,png)<br />
Your task is to produce a program that given the word puzzle and words to be<br />
found in the puzzle, determines, for each word, the position of the first<br />
letter and its orientation in the puzzle.</p>
<p>You can assume that the left upper corner of the puzzle is the origin, (0,0).<br />
Furthemore, the orientation of the word is marked clockwise starting with<br />
letter A for north (note: there are 8 possible directions in total).</p>
<h2 id="输入"><a class="markdownIt-Anchor" href="#输入"></a> 输入</h2>
<p>The first line of input consists of three positive numbers, the number of<br />
lines, 0 &lt; L &lt;= 1000, the number of columns, 0 &lt; C &lt;= 1000, and the number of<br />
words to be found, 0 &lt; W &lt;= 1000. The following L input lines, each one of<br />
size C characters, contain the word puzzle. Then at last the W words are input<br />
one per line.</p>
<h2 id="输出"><a class="markdownIt-Anchor" href="#输出"></a> 输出</h2>
<p>Your program should output, for each word (using the same order as the words<br />
were input) a triplet defining the coordinates, line and column, where the<br />
first letter of the word appears, followed by a letter indicating the<br />
orientation of the word according to the rules define above. Each value in the<br />
triplet must be separated by one space only.</p>
<h2 id="输入样例"><a class="markdownIt-Anchor" href="#输入样例"></a> 输入样例</h2>
<p>20 20 10<br />
QWSPILAATIRAGRAMYKEI<br />
AGTRCLQAXLPOIJLFVBUQ<br />
TQTKAZXVMRWALEMAPKCW<br />
LIEACNKAZXKPOTPIZCEO<br />
FGKLSTCBTROPICALBLBC<br />
JEWHJEEWSMLPOEKORORA<br />
LUPQWRNJOAAGJKMUSJAE<br />
KRQEIOLOAOQPRTVILCBZ<br />
QOPUCAJSPPOUTMTSLPSF<br />
LPOUYTRFGMMLKIUISXSW<br />
WAHCPOIYTGAKLMNAHBVA<br />
EIAKHPLBGSMCLOGNGJML<br />
LDTIKENVCSWQAZUAOEAL<br />
HOPLPGEJKMNUTIIORMNC<br />
LOIUFTGSQACAXMOPBEIO<br />
QOASDHOPEPNBUYUYOBXB<br />
IONIAELOJHSWASMOUTRK<br />
HPOIYTJPLNAQWDRIBITG<br />
LPOINUYMRTEMPTMLMNBO<br />
PAFCOPLHAVAIANALBPFS<br />
MARGARITA<br />
ALEMA<br />
BARBECUE<br />
TROPICAL<br />
SUPREMA<br />
LOUISIANA<br />
CHEESEHAM<br />
EUROPA<br />
HAVAIANA<br />
CAMPONESA</p>
<h2 id="输出样例"><a class="markdownIt-Anchor" href="#输出样例"></a> 输出样例</h2>
<p>0 15 G<br />
2 11 C<br />
7 18 A<br />
4 8 C<br />
16 13 B<br />
4 15 E<br />
10 3 D<br />
5 1 E<br />
19 7 C<br />
11 11 H</p>
<h2 id="瞎翻译"><a class="markdownIt-Anchor" href="#瞎翻译"></a> 瞎翻译</h2>
<p>给你一张字谜图，里头有一堆乱七八糟的字母，<br />
<strong>输入：</strong><br />
先输入仨数L,C,W，前两个(L,C)是字谜图的行数和列数，第三个(W)是输入单词的数目，<br />
之后输入L行C列的数填满字谜图，<br />
最后W行输入W个字符串，这W个字符串肯定都可以在字谜图上找到（字母横着竖着或斜着线性连续）<br />
<strong>输出：</strong><br />
一行输出三个元素，前两个是找到的字符串的首字母的坐标，第三个是字符串的排列方向（从首字母到尾字母的方向），方向一共有8个，按照顺时针旋转，A代表正上方，B代表右上方，一次类推</p>
<h2 id="使用trie树暴力破解"><a class="markdownIt-Anchor" href="#使用trie树暴力破解"></a> 使用trie树暴力破解</h2>
<p><strong>思路：</strong> 用所有所查询的字符串建立一颗trie树，然后遍历地图上的每个点，在每个点分别朝8个方向对trie树搜索（三重循环无脑搜就完了）</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dy[<span class="number">8</span>]=&#123;<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>&#125;;<span class="comment">//设左上角为原点，向下为x轴正方向，向右为y轴正方向</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dx[<span class="number">8</span>]=&#123;<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>&#125;;<span class="comment">//先设置好移动方向，dx[0],dy[0]为向上方向（A方向），方向按照顺时针旋转顺序写</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1005</span>;</span><br><span class="line"><span class="type">char</span> cell[maxn][maxn],word[maxn];<span class="comment">//cell储存字谜地图，word用于接收一个要搜索的单词</span></span><br><span class="line"><span class="type">int</span> slen[maxn],tidx,r,c,w,ans[maxn][<span class="number">3</span>];<span class="comment">//slen储存每个要搜索的单词的长度，tidx为节点序号，ans储存答案（方向+横纵坐标）</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">    <span class="type">int</span> id,next[<span class="number">26</span>];<span class="comment">//在trie树中每个单词的结尾给id赋值，其值为 这个单词按照输入顺序排的序号（从1开始，不是0）</span></span><br><span class="line">&#125;treeN[maxn*maxn];</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//每输入一个单词，进行一次此函数，把单词存入trie树</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,len=<span class="built_in">strlen</span>(word),nxt;</span><br><span class="line">    slen[id]=len;       <span class="comment">//把此字符串的长度储存在len数组中</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        nxt=word[i]-<span class="string">&#x27;A&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(treeN[root].next[nxt]&lt;=<span class="number">0</span>)</span><br><span class="line">            treeN[root].next[nxt]=++tidx;</span><br><span class="line">        root=treeN[root].next[nxt];</span><br><span class="line">    &#125;</span><br><span class="line">    treeN[root].id=id;<span class="comment">//在trie树中每个单词的结尾给id赋值，其值为 这个单词按照输入顺序排的序号（从1开始，不是0）</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//查找函数</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">sch</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y,<span class="type">int</span> dir)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,id;</span><br><span class="line">    <span class="keyword">while</span>(x&gt;=<span class="number">0</span> &amp;&amp; x&lt;=r &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;=c)&#123;    <span class="comment">//在不越界的条件下不断沿trie树搜索</span></span><br><span class="line">        root=treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>];</span><br><span class="line">        <span class="keyword">if</span>(root&lt;=<span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line">        id=treeN[root].id;</span><br><span class="line">        <span class="keyword">if</span>(id&gt;<span class="number">0</span>)&#123;   <span class="comment">//若id&gt;0，说明这个位置是第id个单词的结尾，略微处理得到答案，存入ans数组</span></span><br><span class="line">            ans[id][<span class="number">0</span>]=dir;</span><br><span class="line">            ans[id][<span class="number">1</span>]=x-(slen[id]<span class="number">-1</span>)*dx[dir];</span><br><span class="line">            ans[id][<span class="number">2</span>]=y-(slen[id]<span class="number">-1</span>)*dy[dir];</span><br><span class="line">        &#125;</span><br><span class="line">        x+=dx[dir];</span><br><span class="line">        y+=dy[dir];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    tidx=<span class="number">0</span>;</span><br><span class="line">    std::cin &gt;&gt; r &gt;&gt; c &gt;&gt; w;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        std::cin &gt;&gt; cell[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)&#123;</span><br><span class="line">        std::cin &gt;&gt; word;</span><br><span class="line">        <span class="built_in">joinTree</span>(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)<span class="comment">// 输入所有数据并建立好tire树后暴搜得到答案</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;c; j++)</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;<span class="number">8</span>; k++)</span><br><span class="line">                <span class="built_in">sch</span>(i,j,k);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d %c\n&quot;</span>,ans[i][<span class="number">1</span>],ans[i][<span class="number">2</span>],ans[i][<span class="number">0</span>]+<span class="string">&#x27;A&#x27;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<h2 id="ac自动机解法"><a class="markdownIt-Anchor" href="#ac自动机解法"></a> AC自动机解法</h2>
<p>在trie树的基础上使用AC自动机（只需要多一步添加fail指针，然后再修改亿点点）<br />
AC自动机的好处是只需要在地图最外围的一圈把8个方向都遍历一次就行了，因为它不用像单纯用trie树一样每次只能从根节点开始搜索，而是匹配不成功时通过fail指针转移到树的其他位置继续搜索</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="comment">//相对于暴搜，用AC自动机在地图最外围的一圈把8个方向都遍历一次</span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dy[<span class="number">8</span>]=&#123;<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>&#125;;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dx[<span class="number">8</span>]=&#123;<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>&#125;;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1005</span>;</span><br><span class="line"><span class="type">char</span> cell[maxn][maxn],word[maxn];</span><br><span class="line"><span class="type">int</span> slen[maxn],tidx,r,c,w,ans[maxn][<span class="number">3</span>];</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">    <span class="type">int</span> id,next[<span class="number">26</span>],fail;</span><br><span class="line">&#125;treeN[maxn*maxn];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,len=<span class="built_in">strlen</span>(word),nxt;</span><br><span class="line">    slen[id]=len;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        nxt=word[i]-<span class="string">&#x27;A&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(treeN[root].next[nxt]&lt;=<span class="number">0</span>)</span><br><span class="line">            treeN[root].next[nxt]=++tidx;</span><br><span class="line">        root=treeN[root].next[nxt];</span><br><span class="line">    &#125;</span><br><span class="line">    treeN[root].id=id;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//建立好trie树后调用此函数通过bfs添加fail指针</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">getFail</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> nxt,cur,fail;</span><br><span class="line">    std::queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">        nxt=treeN[<span class="number">0</span>].next[i];</span><br><span class="line">        <span class="keyword">if</span>(nxt&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            treeN[nxt].fail=<span class="number">0</span>;</span><br><span class="line">            q.<span class="built_in">push</span>(nxt);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        cur=q.<span class="built_in">front</span>(),q.<span class="built_in">pop</span>();</span><br><span class="line">        fail=treeN[cur].fail;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">            nxt=treeN[cur].next[i];</span><br><span class="line">            <span class="keyword">if</span>(nxt&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                treeN[nxt].fail=treeN[fail].next[i];</span><br><span class="line">                q.<span class="built_in">push</span>(nxt);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> treeN[cur].next[i]=treeN[fail].next[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ACgo</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y,<span class="type">int</span> dir)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,id;</span><br><span class="line">    <span class="keyword">while</span>(x&gt;=<span class="number">0</span> &amp;&amp; x&lt;=r &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;=c)&#123;</span><br><span class="line">        <span class="keyword">while</span>( root&gt;<span class="number">0</span> &amp;&amp; treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>]&lt;=<span class="number">0</span>)<span class="comment">//如果不能匹配就通过fail指针回溯，在trie的其他位置继续寻找，节约了时间</span></span><br><span class="line">            root=treeN[root].fail;</span><br><span class="line">        root=treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>];</span><br><span class="line">        id=treeN[root].id;</span><br><span class="line">        <span class="keyword">if</span>(id&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            ans[id][<span class="number">0</span>]=dir;</span><br><span class="line">            ans[id][<span class="number">1</span>]=x-(slen[id]<span class="number">-1</span>)*dx[dir];</span><br><span class="line">            ans[id][<span class="number">2</span>]=y-(slen[id]<span class="number">-1</span>)*dy[dir];</span><br><span class="line">        &#125;</span><br><span class="line">        x+=dx[dir];</span><br><span class="line">        y+=dy[dir];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    tidx=<span class="number">0</span>;</span><br><span class="line">    std::cin &gt;&gt; r &gt;&gt; c &gt;&gt; w;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        std::cin &gt;&gt; cell[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)&#123;</span><br><span class="line">        std::cin &gt;&gt; word;</span><br><span class="line">        <span class="built_in">joinTree</span>(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">getFail</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;<span class="number">8</span>; j++)</span><br><span class="line">            <span class="built_in">ACgo</span>(i,<span class="number">0</span>,j),<span class="built_in">ACgo</span>(i,r<span class="number">-1</span>,j);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;c; i++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;<span class="number">8</span>; j++)</span><br><span class="line">            <span class="built_in">ACgo</span>(<span class="number">0</span>,i,j),<span class="built_in">ACgo</span>(c<span class="number">-1</span>,i,j);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d %c\n&quot;</span>,ans[i][<span class="number">1</span>],ans[i][<span class="number">2</span>],ans[i][<span class="number">0</span>]+<span class="string">&#x27;A&#x27;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<h2 id="反向构建trie树不用记录单词长度"><a class="markdownIt-Anchor" href="#反向构建trie树不用记录单词长度"></a> 反向构建trie树，不用记录单词长度</h2>
<p><strong>两段代码都只改了一点，但都时间超限，目前没发现原因，慎看</strong><br />
<strong>两段代码都只改了一点，但都时间超限，目前没发现原因，慎看</strong><br />
<strong>两段代码都只改了一点，但都时间超限，目前没发现原因，慎看</strong><br />
<strong>两段代码都只改了一点，但都时间超限，目前没发现原因，慎看</strong><br />
<strong>两段代码都只改了一点，但都时间超限，目前没发现原因，慎看</strong></p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dy[<span class="number">8</span>]=&#123;<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>&#125;;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dx[<span class="number">8</span>]=&#123;<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>&#125;;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1005</span>;</span><br><span class="line"><span class="type">char</span> cell[maxn][maxn],word[maxn];</span><br><span class="line"><span class="type">int</span> tidx,r,c,w,ans[maxn][<span class="number">3</span>];</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">    <span class="type">int</span> id,next[<span class="number">26</span>],fail;</span><br><span class="line">&#125;treeN[maxn*maxn];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,len=<span class="built_in">strlen</span>(word),nxt;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=len<span class="number">-1</span>; i&gt;=<span class="number">0</span>; i--)&#123;</span><br><span class="line">        nxt=word[i]-<span class="string">&#x27;A&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(treeN[root].next[nxt]&lt;=<span class="number">0</span>)</span><br><span class="line">            treeN[root].next[nxt]=++tidx;</span><br><span class="line">        root=treeN[root].next[nxt];</span><br><span class="line">    &#125;</span><br><span class="line">    treeN[root].id=id;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">getFail</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> nxt,cur,fail;</span><br><span class="line">    std::queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">        nxt=treeN[<span class="number">0</span>].next[i];</span><br><span class="line">        <span class="keyword">if</span>(nxt&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            treeN[nxt].fail=<span class="number">0</span>;</span><br><span class="line">            q.<span class="built_in">push</span>(nxt);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        cur=q.<span class="built_in">front</span>(),q.<span class="built_in">pop</span>();</span><br><span class="line">        fail=treeN[cur].fail;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">            nxt=treeN[cur].next[i];</span><br><span class="line">            <span class="keyword">if</span>(nxt&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                treeN[nxt].fail=treeN[fail].next[i];</span><br><span class="line">                q.<span class="built_in">push</span>(nxt);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> treeN[cur].next[i]=treeN[fail].next[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ACgo</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y,<span class="type">int</span> dir)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,id;</span><br><span class="line">    <span class="keyword">while</span>(x&gt;=<span class="number">0</span> &amp;&amp; x&lt;=r &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;=c)&#123;</span><br><span class="line">        <span class="keyword">while</span>( root&gt;<span class="number">0</span> &amp;&amp; treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>]&lt;=<span class="number">0</span>)</span><br><span class="line">            root=treeN[root].fail;</span><br><span class="line">        root=treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>];</span><br><span class="line">        id=treeN[root].id;</span><br><span class="line">        <span class="keyword">if</span>(id&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            ans[id][<span class="number">0</span>]=dir;</span><br><span class="line">            ans[id][<span class="number">1</span>]=x;</span><br><span class="line">            ans[id][<span class="number">2</span>]=y;</span><br><span class="line">        &#125;</span><br><span class="line">        x+=dx[dir];</span><br><span class="line">        y+=dy[dir];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    tidx=<span class="number">0</span>;</span><br><span class="line">    std::cin &gt;&gt; r &gt;&gt; c &gt;&gt; w;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        std::cin &gt;&gt; cell[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)&#123;</span><br><span class="line">        std::cin &gt;&gt; word;</span><br><span class="line">        <span class="built_in">joinTree</span>(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">getFail</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;<span class="number">8</span>; j++)</span><br><span class="line">            <span class="built_in">ACgo</span>(i,<span class="number">0</span>,j),<span class="built_in">ACgo</span>(i,r<span class="number">-1</span>,j);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;c; i++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;<span class="number">8</span>; j++)</span><br><span class="line">            <span class="built_in">ACgo</span>(<span class="number">0</span>,i,j),<span class="built_in">ACgo</span>(c<span class="number">-1</span>,i,j);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d %c\n&quot;</span>,ans[i][<span class="number">1</span>],ans[i][<span class="number">2</span>],ans[i][<span class="number">0</span>]+<span class="string">&#x27;A&#x27;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​<br />
​<br />
​<br />
​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dy[<span class="number">8</span>]=&#123;<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>&#125;;<span class="comment">//设左上角为原点，向下为x轴正方向，向右为y轴正方向</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> dx[<span class="number">8</span>]=&#123;<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">1</span>&#125;;<span class="comment">//先设置好移动方向，dx[0],dy[0]为向上方向（A方向），方向按照顺时针旋转顺序写</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1005</span>;</span><br><span class="line"><span class="type">char</span> cell[maxn][maxn],word[maxn];<span class="comment">//cell储存字谜地图，word用于接收一个要搜索的单词</span></span><br><span class="line"><span class="type">int</span> tidx,r,c,w,ans[maxn][<span class="number">3</span>];<span class="comment">//tidx为节点序号，ans储存答案（方向+横纵坐标）</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">    <span class="type">int</span> id,next[<span class="number">26</span>];<span class="comment">//在trie树中每个单词的结尾给id赋值，其值为 这个单词按照输入顺序排的序号（从1开始，不是0）</span></span><br><span class="line">&#125;treeN[maxn*maxn];</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//每输入一个单词，进行一次此函数，把单词存入trie树</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,len=<span class="built_in">strlen</span>(word),nxt;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=len<span class="number">-1</span>; i&gt;=<span class="number">0</span>; i--)&#123;</span><br><span class="line">        nxt=word[i]-<span class="string">&#x27;A&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(treeN[root].next[nxt]&lt;=<span class="number">0</span>)</span><br><span class="line">            treeN[root].next[nxt]=++tidx;</span><br><span class="line">        root=treeN[root].next[nxt];</span><br><span class="line">    &#125;</span><br><span class="line">    treeN[root].id=id;<span class="comment">//在trie树中每个单词的结尾给id赋值，其值为 这个单词按照输入顺序排的序号（从1开始，不是0）</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//查找函数</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">sch</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y,<span class="type">int</span> dir)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> root=<span class="number">0</span>,id;</span><br><span class="line">    <span class="keyword">while</span>(x&gt;=<span class="number">0</span> &amp;&amp; x&lt;=r &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;=c)&#123;    <span class="comment">//在不越界的条件下不断沿trie树搜索</span></span><br><span class="line">        root=treeN[root].next[cell[x][y]-<span class="string">&#x27;A&#x27;</span>];</span><br><span class="line">        <span class="keyword">if</span>(root&lt;=<span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line">        id=treeN[root].id;</span><br><span class="line">        <span class="keyword">if</span>(id&gt;<span class="number">0</span>)&#123;   <span class="comment">//若id&gt;0，说明这个位置是第id个单词的结尾，略微处理得到答案，存入ans数组</span></span><br><span class="line">            ans[id][<span class="number">0</span>]=dir;</span><br><span class="line">            ans[id][<span class="number">1</span>]=x;</span><br><span class="line">            ans[id][<span class="number">2</span>]=y;</span><br><span class="line">        &#125;</span><br><span class="line">        x+=dx[dir];</span><br><span class="line">        y+=dy[dir];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    tidx=<span class="number">0</span>;</span><br><span class="line">    std::cin &gt;&gt; r &gt;&gt; c &gt;&gt; w;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)</span><br><span class="line">        std::cin &gt;&gt; cell[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)&#123;</span><br><span class="line">        std::cin &gt;&gt; word;</span><br><span class="line">        <span class="built_in">joinTree</span>(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;r; i++)<span class="comment">// 输入所有数据并建立好tire树后暴搜得到答案</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;c; j++)</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;<span class="number">8</span>; k++)</span><br><span class="line">                <span class="built_in">sch</span>(i,j,k);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=w; i++)</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d %c\n&quot;</span>,ans[i][<span class="number">1</span>],ans[i][<span class="number">2</span>],ans[i][<span class="number">0</span>]+<span class="string">&#x27;A&#x27;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90AC%E8%87%AA%E5%8A%A8%E6%9C%BA%20_%20trie%E6%A0%91%E3%80%91G%20-%20Word%20Puzzles%20%20%20POJ%20-%201204/" data-id="cl2uhoebu000ze4j3eka6hrdx" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" rel="tag">AC自动机</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Trie%E6%A0%91/" rel="tag">Trie树</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" rel="tag">字符串</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【DP】石子合并" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/">【DP】石子合并.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="1-线形石子合并"><a class="markdownIt-Anchor" href="#1-线形石子合并"></a> 1 线形石子合并</h2>
<p>参考题目 <a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/284/">https://www.acwing.com/problem/content/284/</a></p>
<p>题目要求最小代价</p>
<p>大致思路为：<br />
有n组石头排成一条线，<br />
规定把第i组和第i组合并（自己合并自己），代价为0<br />
1.求所有相邻的两堆石头合并的代价<br />
2.求所有相邻的三堆石头合并的代价，之前求出的两堆石头合并的代价可以作为前提<br />
3.求所有相邻的四堆石头合并的代价，之前求出的两堆石头合并的代价和三堆石头合并的代价都可以作为前提<br />
…<br />
n-1.求相邻的n堆石头合并的代价，之前求出的【2，n-1】堆石头合并的代价都可以作为前提</p>
<p>用程序模拟出这个过程便可以求得答案<br />
.</p>
<p>.</p>
<p>使用二维数组dp记录这些代价，首先令所有的dp[i][i]=0<br />
使用一维数组sum记录从第一堆石头到第i堆石头的石头总数<br />
假设要求解dp[4][7] 只需要求<br />
sum[7]-sum[4-1] + min(dp[4] [4]+dp[5] [7],dp[4] [5]+dp[6] [7],dp[4] [6]+dp[7] [7])</p>
<img src="/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/20201008111934601.png" class="" title="看图便于理解">
<p>代码:</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstring><br />
​    #include <algorithm><br />
​    #include <iomanip><br />
​    #include <queue><br />
​    #include <cmath><br />
​    #include <map><br />
​<br />
​    const int N=303;<br />
​    int sum[N],dp[N][N],v[N];<br />
​<br />
​    int main()<br />
​    {<br />
​        int n;<br />
​        std::cin &gt;&gt; n;<br />
​        std::cin &gt;&gt; v[1];<br />
​        sum[0]=0;<br />
​        sum[1]=v[1];<br />
​        for(int i=2; i&lt;=n; i++)<br />
​        {<br />
​            std::cin &gt;&gt; v[i];<br />
​            sum[i]=sum[i-1]+v[i];<br />
​        }<br />
​        memset(dp,1,sizeof(dp));<br />
​        for(int i=1; i&lt;=n; i++) dp[i][i]=0;<br />
​        for(int span=1; span&lt;n ;span++)<br />
​        {// span表示区间长度，如span=1表示这次循环求相邻的两堆石头，span=2表示这次循环求相邻的三堆石头，span=n-1表示求所有n堆石头合并的代价<br />
​            for(int st=1; st+span&lt;=n; st++)<br />
​            {//st表示所求区间的起点，ed表示所求区间的终点，st和ed同步增加，直到求完所有合并相邻span+1堆石头的代价<br />
​                int ed=st+span;<br />
​                for(int tmp=st; tmp&lt;ed; tmp++)//tmp为[st,ed)之间的所有整数，这一步循环用来求从st到ed的最小代价<br />
​                    dp[st][ed]=std::min(dp[st][ed],dp[st][tmp]+dp[tmp+1][ed]-sum[st-1]+sum[ed]);<br />
​            }<br />
​        }<br />
​        std::cout &lt;&lt; dp[1][n] &lt;&lt; std::endl;<br />
​        return 0;<br />
​    }</p>
<p>​</p>
<h2 id="2-环形石子合并"><a class="markdownIt-Anchor" href="#2-环形石子合并"></a> 2 环形石子合并</h2>
<p>这个知识点是我根据上方线形石子合并自己想的,大概有更优的解法吧</p>
<p>参考题目 <a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1880">https://www.luogu.com.cn/problem/P1880</a></p>
<p><strong>把环形拆成线形</strong> 把环形的n堆石头从第1堆石头和第n堆石头之间分开,成为线形,然后再把这n堆在一条线上的石头复制一份,加到第n堆石头末尾.<br />
这样即可模拟以 <strong>每</strong> 一堆石头为起点的 <strong>线形</strong> 石子合并</p>
<p>线形石子合并中for(int st=1; st+span&lt;=n; st++)的st+span&lt;=n是为了把ed限制在ed&lt;=n,现在可以改成st&lt;=n<br />
其他地方基本与线形合并相同</p>
<p>需要注意dp数组的行数没有变成两倍,for(int tmp=st; tmp&lt;ed; tmp++)中如果出现tmp+1&gt;n<br />
若要获取dp[tmp+1][ed]的值,则获取tmp[tmp+1-n][ed-n]的值</p>
<img src="/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/20201008111347129.png" class="" title="看图便于理解">  
<p>代码:</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstring><br />
​    #include <algorithm><br />
​    #include <iomanip><br />
​    #include <queue><br />
​    #include <cmath><br />
​    #include <map><br />
​<br />
​    const int N=103;<br />
​    int sum[N&lt;&lt;1],dp[N][N&lt;&lt;1],v[N],pd[N][N&lt;&lt;1];<br />
​<br />
​    int main()<br />
​    {<br />
​        int n;<br />
​        std::cin &gt;&gt; n;<br />
​        std::cin &gt;&gt; v[1];<br />
​        sum[0]=0;<br />
​        sum[1]=v[1];<br />
​        for(int i=2; i&lt;=n; i++)<br />
​        {<br />
​            std::cin &gt;&gt; v[i];<br />
​            sum[i]=sum[i-1]+v[i];<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++)<br />
​        {<br />
​            sum[i+n]=sum[i+n-1]+v[i];<br />
​        }<br />
​        memset(dp,1,sizeof(dp));<br />
​        memset(pd,0,sizeof(pd));<br />
​        for(int i=1; i&lt;=n; i++)<br />
​        {<br />
​            dp[i][i]=0;<br />
​            pd[i][i]=0;<br />
​        }<br />
​        for(int span=1; span&lt;n ;span++)<br />
​        {<br />
​            for(int st=1; st&lt;=n; st++)<br />
​            {<br />
​                int ed=st+span;<br />
​                for(int tmp=st; tmp&lt;ed; tmp++)<br />
​                {<br />
​                    if(tmp+1&gt;n)<br />
​                    {<br />
​                        dp[st][ed]=std::min(dp[st][ed],dp[st][tmp]+dp[tmp+1-n][ed-n]-sum[st-1]+sum[ed]);<br />
​                        pd[st][ed]=std::max(pd[st][ed],pd[st][tmp]+pd[tmp+1-n][ed-n]-sum[st-1]+sum[ed]);<br />
​                    }<br />
​                    else<br />
​                    {<br />
​                        dp[st][ed]=std::min(dp[st][ed],dp[st][tmp]+dp[tmp+1][ed]-sum[st-1]+sum[ed]);<br />
​                        pd[st][ed]=std::max(pd[st][ed],pd[st][tmp]+pd[tmp+1][ed]-sum[st-1]+sum[ed]);<br />
​                    }<br />
​                }<br />
​            }<br />
​        }<br />
​        int mn=1e9,mx=0;<br />
​        for(int i=1; i&lt;=n; i++)<br />
​        {<br />
​            mn=std::min(dp[i][n+i-1],mn);<br />
​            mx=std::max(pd[i][n+i-1],mx);<br />
​        }<br />
​        std::cout &lt;&lt; mn &lt;&lt; std::endl &lt;&lt; mx;<br />
​        return 0;<br />
​    }</p>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/" data-id="cl2uhoebv0011e4j3fhdb2vs1" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【KM算法】B - Going Home POJ - 2195" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/">【KM算法】B - Going Home POJ - 2195.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p><a target="_blank" rel="noopener" href="https://vjudge.net/contest/389071#problem/B">https://vjudge.net/contest/389071#problem/B</a></p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>On a grid map there are n little men and n houses. In each unit time, every<br />
little man can move one unit step, either horizontally, or vertically, to an<br />
adjacent point. For each little man, you need to pay a $1 travel fee for every<br />
step he moves, until he enters a house. The task is complicated with the<br />
restriction that each house can accommodate only one little man.</p>
<p>Your task is to compute the minimum amount of money you need to pay in order<br />
to send these n little men into those n different houses. The input is a map<br />
of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that<br />
point, and am ‘m’ indicates there is a little man on that point.</p>
<p>![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuLzI5ZGE0YzIyY2Q5YTM1ZWI5NmIyYTA4Yjc1Y2U4NDIw?x-oss-">https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuLzI5ZGE0YzIyY2Q5YTM1ZWI5NmIyYTA4Yjc1Y2U4NDIw?x-oss-</a><br />
process=image/format,png#pic_center)</p>
<p>You can think of each point on the grid map as a quite large square, so it can<br />
hold n little men at the same time; also, it is okay if a little man steps on<br />
a grid with a house without entering that house.</p>
<h2 id="输入"><a class="markdownIt-Anchor" href="#输入"></a> 输入</h2>
<p>There are one or more test cases in the input. Each case starts with a line<br />
giving two integers N and M, where N is the number of rows of the map, and M<br />
is the number of columns. The rest of the input will be N lines describing the<br />
map. You may assume both N and M are between 2 and 100, inclusive. There will<br />
be the same number of 'H’s and 'm’s on the map; and there will be at most 100<br />
houses. Input will terminate with 0 0 for N and M.</p>
<h2 id="输出"><a class="markdownIt-Anchor" href="#输出"></a> 输出</h2>
<p>For each test case, output one line with the single integer, which is the<br />
minimum amount, in dollars, you need to pay.</p>
<h2 id="样例输入"><a class="markdownIt-Anchor" href="#样例输入"></a> 样例输入</h2>
<p>2 2<br />
.m<br />
H.<br />
5 5<br />
HH…m<br />
…<br />
…<br />
…<br />
mm…H<br />
7 8<br />
…H…<br />
…H…<br />
…H…<br />
mmmHmmmm<br />
…H…<br />
…H…<br />
…H…<br />
0 0</p>
<h2 id="样例输出"><a class="markdownIt-Anchor" href="#样例输出"></a> 样例输出</h2>
<p>2<br />
10<br />
28</p>
<h2 id="瞎翻译"><a class="markdownIt-Anchor" href="#瞎翻译"></a> 瞎翻译</h2>
<p>给你一张地图，地图被分割成了N行M列的网格。</p>
<p>第一行：输入N，M表示地图大小。</p>
<p>第2 到 第N+1行： 输入地图内容， .代表空地，m代表人，H代表房子。</p>
<p>N和M不大于100，房子数目不大于100</p>
<p>人和房子的数量是相等的，而人要移动进入房子，且每个房子只能进一个人。<br />
不过人每移动一格（横移或者竖移）要花一块钱。</p>
<p><strong>问：</strong><br />
要使人都进入房子最少花多少钱？<br />
（地图的每一格都足够大，可以容纳无限多的人。）</p>
<h2 id="题解"><a class="markdownIt-Anchor" href="#题解"></a> 题解</h2>
<p>思路：<br />
<strong>1.</strong><br />
地图最大为100x100 ，所以人最多花不到200元钱，我们定一个常数ML=210.<br />
<strong>2.</strong><br />
先计算每个人到每个房子需要花的钱，用ML减去需要花的钱，得到的数值，存进数组map[][]（不是地图，我取的映射的意思）</p>
<p>这么存的原因是：KM算法可以算出最多要花多少钱，然而我们需要求最少要花多少钱，这样就只需要把“最小的”先暂时变成“最大的”，完成KM算法之后再额外通过一步计算得到正确答案。</p>
<p>推导可知：正确答案=（ML*房子数量）-KM算法得到的最大值</p>
<p>​<br />
​    #include <cstdio><br />
​    #include <iostream><br />
​    #include <algorithm><br />
​    #include <cstring><br />
​<br />
const int maxn=110;<br />
const int ML=220;//花费不可能超过200<br />
char cell[maxn][maxn];<br />
int map[maxn][maxn],lx[maxn],ly[maxn],link[maxn];<br />
//map取的意思是映射，map[i][j]表示第i个人到第j个房子的距离<br />
//lx表示人顶标的值，ly表示房子顶标的值<br />
bool visx[maxn],visy[maxn];<br />
int pnum,ans;<br />
struct Node<br />
{<br />
int x,y;<br />
}person[maxn],house[maxn];</p>
<pre><code>bool dfs(int x)
&#123;

    visx[x]=true;
    for(int i=0; i&lt;pnum ;i++)
    &#123;
//这里的lx[x]一开始写成了lx[i]，找bug找了半天，巨麻烦，打标记警醒一下
        if(!visy[i] &amp;&amp; lx[x]+ly[i]==map[x][i])
        &#123;
            visy[i]=true;
            if(link[i]==-1 || dfs(link[i]))
            &#123;
                link[i]=x;
                return true;
            &#125;
        &#125;
    &#125;
    return false;
&#125;

int km()
&#123;
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(link,-1,sizeof(link));
    for(int i=0; i&lt;pnum ; i++)
        for(int j=0; j&lt;pnum; j++)
        &#123;
            lx[i]=std::max(lx[i],map[i][j]);
        &#125;
    for(int i=0; i&lt;pnum; i++)
    &#123;
        memset(visx,false,sizeof(visx));
        memset(visy,false,sizeof(visy));
        while(!dfs(i))
        &#123;
            int tmp=ML;

//---------------------------&gt;&gt;特此标记&lt;&lt;-----------------------------
// KM没学好，这里一开始想错了，误认为下面tmp=min（）式子中lx的下标一定是i，
//导致下方两行没要，一直错被卡了很长时间

            for(int j=0; j&lt;pnum; j++)
                if(visx[j])
//*******************************************************************************
                    for(int k=0; k&lt;pnum; k++)
                        if(visy[k]==false)
                            tmp=std::min(tmp,lx[j]+ly[k]-map[j][k]);
            for(int j=0; j&lt;pnum; j++)
            &#123;
                if(visx[j])
                    lx[j]-=tmp;
                if(visy[j])
                    ly[j]+=tmp;
            &#125;
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
        &#125;
    &#125;
    ans=0;
    for(int i=0;i&lt;pnum; i++)
    &#123;
        ans+=lx[i]+ly[i];
    &#125;
    return ML*pnum-ans;
&#125;

int main()
&#123;
    int n,m;
    int p,h;
    while(std::cin &gt;&gt; n &gt;&gt; m &amp;&amp; !(n==0 &amp;&amp; m==0))
    &#123;
        p=h=0;
        for(int i=0;i &lt;n; i++)
            for(int j=0; j&lt;m ; j++)
            &#123;
                std::cin &gt;&gt; cell[i][j];
                if(cell[i][j]=='m')
                &#123;
                    person[p].x=i;
                    person[p++].y=j;
                &#125;
                else if(cell[i][j]=='H')
                &#123;
                    house[h].x=i;
                    house[h++].y=j;
                &#125;
            &#125;
        pnum=p;
        for(int i=0; i&lt;p; i++)
            for(int j=0; j&lt;h; j++)
            &#123;
                map[i][j]=abs(person[i].x-house[j].x)+abs(person[i].y-house[j].y);
                map[i][j]=ML-map[i][j];
            &#125;
        std::cout &lt;&lt; km() &lt;&lt; std::endl;
    &#125;

    return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/" data-id="cl2uhoebx0015e4j3021z83ha" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/KM%E7%AE%97%E6%B3%95/" rel="tag">KM算法</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E4%BA%8C%E5%88%86%E5%9B%BE/" rel="tag">二分图</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/">【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>倍增 构造O(nlogn)，在线(单次)查询O(logn)<br />
tarjin 构造O(n) ，离线(全部)查询O(N+M)<br />
根据题目 <strong>洛谷P3379【模板】最近公共祖先</strong> 的样例测试，tarjin和倍增不能通过占用的时间或空间评判高下，谁占优势应该跟数据的特征有关。</p>
<h2 id="洛谷p3379模板最近公共祖先"><a class="markdownIt-Anchor" href="#洛谷p3379模板最近公共祖先"></a> 洛谷P3379【模板】最近公共祖先</h2>
<p>倍增方法</p>
<blockquote>
<p>构造fa数组的正确写法是这样的<br />
for(int i=1; i&lt;=20; i++){<br />
fa[x][i] = fa[fa[x][i-1]][i-1];<br />
}<br />
然而第一遍错写成了这样<br />
for(int i=1; i&lt;=20; i++){<br />
fa[x][i] = fa[father][i-1];<br />
}<br />
这显然是错误的，不是方法他的父亲的上2<sup>i-1个节点，而是访问它的上2</sup>i-1个节点的上2^i-1个节点<br />
引以为戒</p>
</blockquote>
<pre><code>#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;queue&gt;
#include &lt;map&gt;
#include &lt;stack&gt;
#include &lt;string&gt;
#include &lt;cstring&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;
#include &lt;set&gt;
typedef long long int LL;
const int N = 5e5+5;
int fa[N][22],depth[N],head[N];
int n,m,s,u,v;
int idx;
struct Edge
&#123;
    int to,nxt;
&#125;edg[N&lt;&lt;1];
void addEdge(int fr,int to)
&#123;
    edg[idx].to = to;
    edg[idx].nxt = head[fr];
    head[fr] = idx++;
&#125;
void build(int x,int father)
&#123;
    fa[x][0] = father;
    depth[x] = depth[father]+1;
    for(int i=1; i&lt;=20; i++)&#123;
        fa[x][i] = fa[fa[x][i-1]][i-1];
    &#125;
    for(int e=head[x]; e; e=edg[e].nxt)&#123;
        int y = edg[e].to;
        if(y!=father) build(y,x);
    &#125;
&#125;
int lca(int x,int y)
&#123;
    if(depth[x] &lt; depth[y]) std::swap(x,y);
    for(int i=20; i&gt;=0; i--)&#123;
        if(fa[x][i]) if(depth[fa[x][i]]&gt;=depth[y])&#123;
            x = fa[x][i];
            if(depth[x] == depth[y]) break;
        &#125;
    &#125;
    if(x == y) return x;
    for(int i=20; i&gt;=0; i--)&#123;
        if(fa[x][i]) if(fa[x][i] != fa[y][i])&#123;
            x = fa[x][i];
            y = fa[y][i];
        &#125;
    &#125;
    return fa[y][0];
&#125;
int main()
&#123;
    //freopen(&quot;D:\\EdgeDownloadPlace\\P3379_2.in&quot;,&quot;r&quot;,stdin);
    idx = 2;
    scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);
    for(int i=1; i&lt;n; i++)&#123;
        scanf(&quot;%d%d&quot;,&amp;u,&amp;v);
        addEdge(u,v); addEdge(v,u);
    &#125;
    build(s,0);
    for(int i=0; i&lt;m; i++)&#123;
        scanf(&quot;%d%d&quot;,&amp;u,&amp;v);
        printf(&quot;%d\n&quot;,lca(u,v));
    &#125;
    return 0;
&#125;
</code></pre>
<p>倍增方法可以提前算log优化</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 5e5+5;<br />
​    int fa[N][22],depth[N],head[N],old_brother[N];<br />
​    int n,m,s,u,v;<br />
​    int idx;<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt;<br />
​    }edg[N&lt;&lt;1];<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​        edg[idx].to = to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    void build(int x,int father)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        depth[x] = depth[father]+1;<br />
​<br />
​        for(int i=1; i&lt;=old_brother[depth[x]]; i++){<br />
​        //for(int i=1; i&lt;=20; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​        }<br />
​<br />
for(int e=head[x]; e; e=edg[e].nxt){<br />
int y = edg[e].to;<br />
if(y!=father) build(y,x);<br />
}<br />
}<br />
int lca(int x,int y)<br />
{<br />
if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
//<br />
/*<br />
for(int i=20; i&gt;=0; i–){<br />
if(fa[x][i]) if(depth[fa[x][i]]&gt;=depth[y]){<br />
x = fa[x][i];<br />
if(depth[x] == depth[y]) break;<br />
}<br />
}<br />
*/<br />
while(depth[x] &gt; depth[y]){<br />
x = fa[x][old_brother[depth[x]-depth[y]]-1];<br />
}<br />
///<br />
if(x == y) return x;<br />
for(/<em>int i=20;</em>/ int i=old_brother[depth[x]]-1; i&gt;=0; i–){<br />
if(fa[x][i] != fa[y][i]){<br />
x = fa[x][i];<br />
y = fa[y][i];<br />
}<br />
}<br />
return fa[y][0];<br />
}<br />
int main()<br />
{<br />
//freopen(“D:\EdgeDownloadPlace\P3379_2.in”,“r”,stdin);<br />
idx = 2;<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
for(int i=1; i&lt;n; i++){<br />
scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
addEdge(u,v); addEdge(v,u);<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
old_brother[i] = old_brother[i-1] + (1 &lt;&lt; old_brother[i-1] == i);<br />
}<br />
build(s,0);<br />
for(int i=0; i&lt;m; i++){<br />
scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
printf(&quot;%d\n&quot;,lca(u,v));<br />
}<br />
return 0;<br />
}</p>
<p>​</p>
<p>tarjin方法</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstring><br />
​    #include <string><br />
​    #include <cstdlib><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <stack><br />
​    #include <vector><br />
​    #include <set><br />
​    #include <map><br />
​    typedef long long int LL;<br />
​    //typedef std::pair&lt;int ,int&gt; PP;<br />
​    const int N = 5e5+5, M = 1e6+5, INF = 0x7fffffff;<br />
​    int n, m, u, v, s;<br />
​    int idx,qidx;<br />
​    int head[N],sset[N],vis[N],ans[N],qhead[N];<br />
​    struct Edge<br />
​    {<br />
​        int to, nxt;<br />
​    } edg[M];<br />
​    struct QEdge<br />
​    {<br />
​        int to, nxt, id;<br />
​    } qedg[M];<br />
​    void initial()<br />
​    {<br />
​        idx = qidx = 2;<br />
​        for (int i = 0; i &lt; N; i++)<br />
​            sset[i] = i;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int  y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​        edg[idx].to = to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    void qaddEdge(int fr,int to,int id)<br />
​    {<br />
​        qedg[qidx].to = to;<br />
​        qedg[qidx].nxt = qhead[fr];<br />
​        qedg[qidx].id = id;<br />
​        qhead[fr] = qidx++;<br />
​    }<br />
​    void tarjin(int x,int fr)<br />
​    {<br />
​        for (int e = head[x]; e; e=edg[e].nxt){<br />
​            if((e^1) == fr)<br />
​                continue;<br />
​            int y = edg[e].to;<br />
​            tarjin(y,e);<br />
​            mmerge(y, x);<br />
​        }<br />
​        for (int e = qhead[x]; e; e=qedg[e].nxt){<br />
​            int y = qedg[e].to;<br />
​            if(vis[y])<br />
​                ans[qedg[e].id] = ffind(y);<br />
​        }<br />
​        vis[x] = 1;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
​        for (int i = 1; i &lt; n; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            addEdge(u, v);<br />
​            addEdge(v, u);<br />
​        }<br />
​        for (int i = 0; i &lt; m; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            qaddEdge(u, v, i);<br />
​            qaddEdge(v, u, i);<br />
​        }<br />
​        tarjin(s,0);<br />
​        for (int i = 0; i &lt; m; i++)<br />
​            printf(&quot;%d\n&quot;,ans[i]);<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p1967-noip2013-提高组-货车运输"><a class="markdownIt-Anchor" href="#洛谷-p1967-noip2013-提高组-货车运输"></a> 洛谷 P1967 [NOIP2013 提高组] 货车运输</h2>
<p>最大生成树 + 倍增lca找最短距离<br />
注意应该先更新ans，再使当前点倍增跳跃，刚才是有一处写反了，没注意到，导致WA</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 1e4+4, M = 5e4+4, INF = 0x7fffffff, LM = 14;<br />
​    int n,m,u,v,w,k,ans;<br />
​    int idx;<br />
​    int head[N],sset[N],fa[N][LM+1],dis[N][LM+1],depth[N],vis[N];<br />
​    struct Esave<br />
​    {<br />
​        int fr,to,w;<br />
​    }es[M&lt;&lt;1];<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt,w;<br />
​    }edg[M&lt;&lt;1];<br />
​    void addE(int u,int v,int w)<br />
​    {<br />
​        edg[idx].to = v;<br />
​        edg[idx].nxt = head[u];<br />
​        edg[idx].w = w;<br />
​        head[u] = idx++;<br />
​    }<br />
​    void initial()<br />
​    {<br />
​        idx = 2;<br />
​        for(int i=0; i&lt;N; i++) sset[i] = i;<br />
​    }<br />
​    bool escmp(Esave x,Esave y)<br />
​    {<br />
​        return x.w &gt; y.w;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void build(int x,int father,int d)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        dis[x][0] = d;<br />
​        depth[x] = depth[father] + 1;<br />
​        for(int i=1; i&lt;=LM; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​            dis[x][i] = std::min(dis[fa[x][i-1]][i-1],dis[x][i-1]);<br />
​        }<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            if(edg[e].to != father) build(edg[e].to,x,edg[e].w);<br />
​        }<br />
​    }<br />
​    int lca(int x,int y)<br />
​    {<br />
​        ans = INF;<br />
​        if(ffind(x) != ffind(y)) return -1;<br />
​        if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(depth[fa[x][i]] &gt;= depth[y]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                x = fa[x][i];<br />
​            }<br />
​            if(depth[x] == depth[y]) break;<br />
​        }<br />
​        if(x == y) return ans;<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(fa[x][i] != fa[y][i]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                ans = std::min(ans,dis[y][i]);<br />
​                x = fa[x][i];<br />
​                y = fa[y][i];<br />
​            }<br />
​        }<br />
​        return std::min(ans,std::min(dis[x][0],dis[y][0]));<br />
​        //return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​        for(int i=0; i&lt;m; i++) scanf(&quot;%d%d%d&quot;,&amp;es[i].fr,&amp;es[i].to,&amp;es[i].w);<br />
​        std::sort(es,es+m,escmp);<br />
​        for(int i=0; i&lt;m;  i++){<br />
​            u = es[i].fr, v = es[i].to, w = es[i].w;<br />
​            if(ffind(u) != ffind(v)){<br />
​                mmerge(u,v);<br />
​                addE(u,v,w); addE(v,u,w);<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) if(!vis[ffind(i)]){<br />
​            vis[ffind(i)] = 1;<br />
​            build(i,0,0);<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;k);<br />
​        while(k–){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            printf(&quot;%d\n&quot;,lca(u,v));<br />
​        }<br />
​        return 0;<br />
​    }</p>
<p>求log优化版</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 1e4+4, M = 5e4+4, INF = 0x7fffffff, LM = 14;<br />
​    int n,m,u,v,w,k,ans;<br />
​    int idx;<br />
​    int head[N],sset[N],fa[N][LM+1],dis[N][LM+1],depth[N],vis[N],lg[N];<br />
​    struct Esave<br />
​    {<br />
​        int fr,to,w;<br />
​    }es[M&lt;&lt;1];<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt,w;<br />
​    }edg[M&lt;&lt;1];<br />
​    void addE(int u,int v,int w)<br />
​    {<br />
​        edg[idx].to = v;<br />
​        edg[idx].nxt = head[u];<br />
​        edg[idx].w = w;<br />
​        head[u] = idx++;<br />
​    }<br />
​    void initial()<br />
​    {<br />
​        idx = 2;<br />
​        for(int i=0; i&lt;N; i++) sset[i] = i;<br />
​        for(int i=1; i&lt;N; i++) lg[i] = lg[i-1] + (1 &lt;&lt; lg[i-1] == i);<br />
​    }<br />
​    bool escmp(Esave x,Esave y)<br />
​    {<br />
​        return x.w &gt; y.w;<br />
​    }<br />
​    int ffind(int x)<br />
​    {<br />
​        return sset[x] == x ? x : sset[x] = ffind(sset[x]);<br />
​    }<br />
​    void mmerge(int x,int y)<br />
​    {<br />
​        sset[ffind(x)] = ffind(y);<br />
​    }<br />
​    void build(int x,int father,int d)<br />
​    {<br />
​        fa[x][0] = father;<br />
​        dis[x][0] = d;<br />
​        depth[x] = depth[father] + 1;<br />
​        for(int i=1; i&lt;=lg[depth[x]]-1; i++){<br />
​            fa[x][i] = fa[fa[x][i-1]][i-1];<br />
​            dis[x][i] = std::min(dis[fa[x][i-1]][i-1],dis[x][i-1]);<br />
​        }<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            if(edg[e].to != father) build(edg[e].to,x,edg[e].w);<br />
​        }<br />
​    }<br />
​    int lca(int x,int y)<br />
​    {<br />
​        ans = INF;<br />
​        if(ffind(x) != ffind(y)) return -1;<br />
​        if(depth[x] &lt; depth[y]) std::swap(x,y);<br />
​        /*<br />
​        for(int i=LM; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(depth[fa[x][i]] &gt;= depth[y]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                x = fa[x][i];<br />
​            }<br />
​            if(depth[x] == depth[y]) break;<br />
​        }<br />
​        <em>/<br />
​        *<br />
​        while(depth[x] &gt; depth[y]){<br />
​            u = lg[depth[x]-depth[y]]-1;<br />
​            ans = std::min(ans,dis[x][u]);<br />
​            x = fa[x][u];<br />
​        }<br />
​        //</em>/<br />
​        if(x == y) return ans;<br />
​        for(int i=lg[depth[x]]-1; i&gt;=0; i–){<br />
​            if(fa[x][i]) if(fa[x][i] != fa[y][i]){<br />
​                ans = std::min(ans,dis[x][i]);<br />
​                ans = std::min(ans,dis[y][i]);<br />
​                x = fa[x][i];<br />
​                y = fa[y][i];<br />
​            }<br />
​        }<br />
​        return std::min(ans,std::min(dis[x][0],dis[y][0]));<br />
​        //return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​        for(int i=0; i&lt;m; i++) scanf(&quot;%d%d%d&quot;,&amp;es[i].fr,&amp;es[i].to,&amp;es[i].w);<br />
​        std::sort(es,es+m,escmp);<br />
​        for(int i=0; i&lt;m;  i++){<br />
​            u = es[i].fr, v = es[i].to, w = es[i].w;<br />
​            if(ffind(u) != ffind(v)){<br />
​                mmerge(u,v);<br />
​                addE(u,v,w); addE(v,u,w);<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) if(!vis[ffind(i)]){<br />
​            vis[ffind(i)] = 1;<br />
​            build(i,0,0);<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;k);<br />
​        while(k–){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            printf(&quot;%d\n&quot;,lca(u,v));<br />
​        }<br />
​        return 0;<br />
​    }</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" data-id="cl2uhoeby0018e4j3como9hfl" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LCA/" rel="tag">LCA</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879%5BTJOI2010%5D%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879%5BTJOI2010%5D%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/">【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%AD%97%E7%AC%A6%E4%B8%B2/">字符串</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3879tjoi2010阅读理解"><a class="markdownIt-Anchor" href="#洛谷-p3879tjoi2010阅读理解"></a> 洛谷 P3879[TJOI2010]阅读理解</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int INF = 0x7fffffff, SCF = 0x3fffffff;<br />
​    const int N = 5e6+4, M = 1e3+4;<br />
​    int n,m,k;<br />
​    int idx,len,ans;<br />
​    int has[M];<br />
​    char ss[22];<br />
​    struct TT<br />
​    {<br />
​        int nxt[26],id;<br />
​    }tree[N];<br />
​    void jointree(int rt)<br />
​    {<br />
​        len = strlen(ss);<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]){<br />
​                tree[rt].nxt[pp] = idx++;<br />
​            }<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        tree[rt].id = 1;<br />
​    }<br />
​    void qry(int rt)<br />
​    {<br />
​        int root = rt;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]) return ;<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        has[root] = tree[rt].id;<br />
​    }<br />
​    void solve()<br />
​    {<br />
​        memset(has,0,sizeof(has));<br />
​        len = strlen(ss);<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            qry(i);<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(has[i]) printf(&quot;%d “,i);<br />
​        }<br />
​        printf(”\n&quot;);<br />
​    }<br />
​    int main()<br />
​    {<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        idx = n+1;<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            scanf(&quot;%d&quot;,&amp;k);<br />
​            for(int j=1; j&lt;=k; j++){<br />
​                scanf(&quot;%s&quot;,ss);<br />
​                jointree(i);<br />
​            }<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;m);<br />
​        for(int i=0; i&lt;m; i++){<br />
​            scanf(&quot;%s&quot;,ss);<br />
​            solve();<br />
​        }<br />
​        return 0;<br />
​    }</p>
<p>​</p>
<h2 id="洛谷-p3808-模板ac自动机简单版"><a class="markdownIt-Anchor" href="#洛谷-p3808-模板ac自动机简单版"></a> 洛谷 P3808 【模板】AC自动机（简单版）</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int INF = 0x7fffffff, SCF = 0x3fffffff;<br />
​    const int N = 1e7+4, M = 1e3+4;<br />
​    int n,idx;<br />
​    char ss[N];<br />
​    struct TT<br />
​    {<br />
​        int fail,id,nxt[26];<br />
​    }tree[N];<br />
​    void joinTree()<br />
​    {<br />
​        int len = strlen(ss), rt = 0;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]){<br />
​                tree[rt].nxt[pp] = idx++;<br />
​            }<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        tree[rt].id += 1;<br />
​    }<br />
​    void getFail()<br />
​    {<br />
​        std::queue<int> q;<br />
​        int x,y,fail;<br />
​        for(int i=0; i&lt;26; i++){<br />
​            y = tree[0].nxt[i];<br />
​            if(y&gt;0){<br />
​                tree[y].fail = 0;<br />
​                q.push(y);<br />
​            }<br />
​        }<br />
​        while(!q.empty()){<br />
​            x = q.front(); q.pop();<br />
​            fail = tree[x].fail;<br />
​            for(int i=0; i&lt;26; i++){<br />
​                y = tree[x].nxt[i];<br />
​                if(y&gt;0){<br />
​                    tree[y].fail = tree[fail].nxt[i];<br />
​                    q.push(y);<br />
​                }<br />
​                else tree[x].nxt[i] = tree[fail].nxt[i];<br />
​            }<br />
​        }<br />
​    }<br />
​    int ACgo()<br />
​    {<br />
​        int rt = 0,len = strlen(ss),ans = 0;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            rt = tree[rt].nxt[ss[i]-‘a’];<br />
​            for(int j=rt; j &amp;&amp; tree[j].id != -1; j=tree[j].fail){<br />
​                ans += tree[j].id;<br />
​                tree[j].id = -1;<br />
​            }<br />
​        }<br />
​        return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        //freopen(“D:\EdgeDownloadPlace\P3808_2.in”,“r”,stdin);<br />
​        idx = 1;<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        while(n–){<br />
​            scanf(&quot;%s&quot;,ss);<br />
​            joinTree();<br />
​        }<br />
​        getFail();<br />
​        scanf(&quot;%s&quot;,ss);<br />
​        printf(&quot;%d&quot;,ACgo());<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p3796-模板ac自动机加强版"><a class="markdownIt-Anchor" href="#洛谷-p3796-模板ac自动机加强版"></a> 洛谷 P3796 【模板】AC自动机（加强版）</h2>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> <span class="type">int</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> INF = <span class="number">0x7fffffff</span>, SCF = <span class="number">0x3fffffff</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1e6</span>+<span class="number">4</span>, M = <span class="number">10550</span>;</span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="type">int</span> idx;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">TT</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> fail,id,nxt[<span class="number">26</span>];</span><br><span class="line">&#125;node[M];</span><br><span class="line"><span class="type">char</span> ss[N];</span><br><span class="line"><span class="type">char</span> sub[<span class="number">155</span>][<span class="number">75</span>];</span><br><span class="line"><span class="type">int</span> save[<span class="number">155</span>];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">initial</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;=idx; i++)&#123;</span><br><span class="line">        <span class="built_in">memset</span>(node[i].nxt,<span class="number">0</span>,<span class="built_in">sizeof</span>(node[i].nxt));</span><br><span class="line">        node[i].fail = <span class="number">0</span>;</span><br><span class="line">        node[i].id = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    idx = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">memset</span>(save,<span class="number">0</span>,<span class="built_in">sizeof</span>(save));</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> len = <span class="built_in">strlen</span>(sub[id]) ,rt = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        <span class="type">int</span> ch = sub[id][i]-<span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(!node[rt].nxt[ch]) node[rt].nxt[ch] = ++idx;</span><br><span class="line">        rt = node[rt].nxt[ch];</span><br><span class="line">    &#125;</span><br><span class="line">    node[rt].id = id;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">buildFail</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    std::queue&lt;<span class="type">int</span> &gt;q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(node[<span class="number">0</span>].nxt[i]&gt;<span class="number">0</span>) &#123;</span><br><span class="line">            node[node[<span class="number">0</span>].nxt[i]].fail = <span class="number">0</span>;</span><br><span class="line">            q.<span class="built_in">push</span>(node[<span class="number">0</span>].nxt[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        <span class="type">int</span> cur = q.<span class="built_in">front</span>(); q.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> fail = node[cur].fail;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">            <span class="type">int</span> next = node[cur].nxt[i];</span><br><span class="line">            <span class="keyword">if</span>(next&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                node[next].fail = node[fail].nxt[i];</span><br><span class="line">                q.<span class="built_in">push</span>(next);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> node[cur].nxt[i] = node[fail].nxt[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ACgo</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> len = <span class="built_in">strlen</span>(ss),rt = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        rt = node[rt].nxt[ss[i]-<span class="string">&#x27;a&#x27;</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=rt; j; j=node[j].fail)</span><br><span class="line">            save[node[j].id] += <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//freopen(&quot;D:\\EdgeDownloadPlace\\P3796_1.in&quot;,&quot;r&quot;,stdin);</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n))&#123;</span><br><span class="line">        <span class="keyword">if</span>(n == <span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line">        <span class="built_in">initial</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,sub[i]);</span><br><span class="line">            <span class="built_in">joinTree</span>(i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">buildFail</span>();</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,ss);</span><br><span class="line">        <span class="built_in">ACgo</span>();</span><br><span class="line">        <span class="type">int</span> mx = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            mx = std::<span class="built_in">max</span>(save[i],mx);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,mx);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(save[i] == mx)&#123;</span><br><span class="line">                <span class="built_in">printf</span>(<span class="string">&quot;%s\n&quot;</span>,sub[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879[TJOI2010]%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/" data-id="cl2uhoec2001ce4j32ycqbr2u" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" rel="tag">AC自动机</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Trie%E6%A0%91/" rel="tag">Trie树</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" rel="tag">字符串</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【tarjin算法练习 缩点，割点，割边】洛谷_P3387缩点模板P3388割点模板 HDU4738 caocao‘bridge" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90tarjin%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0%20%E7%BC%A9%E7%82%B9%EF%BC%8C%E5%89%B2%E7%82%B9%EF%BC%8C%E5%89%B2%E8%BE%B9%E3%80%91%E6%B4%9B%E8%B0%B7_P3387%E7%BC%A9%E7%82%B9%E6%A8%A1%E6%9D%BFP3388%E5%89%B2%E7%82%B9%E6%A8%A1%E6%9D%BF%20HDU4738%20caocao%E2%80%98bridge/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90tarjin%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0%20%E7%BC%A9%E7%82%B9%EF%BC%8C%E5%89%B2%E7%82%B9%EF%BC%8C%E5%89%B2%E8%BE%B9%E3%80%91%E6%B4%9B%E8%B0%B7_P3387%E7%BC%A9%E7%82%B9%E6%A8%A1%E6%9D%BFP3388%E5%89%B2%E7%82%B9%E6%A8%A1%E6%9D%BF%20HDU4738%20caocao%E2%80%98bridge/">【tarjin算法练习 缩点，割点，割边】洛谷_P3387缩点模板P3388割点模板 HDU4738 caocao‘bridge.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3387缩点模板"><a class="markdownIt-Anchor" href="#洛谷-p3387缩点模板"></a> 洛谷 P3387缩点模板</h2>
<p>vis数组是必要的，如果遇到vis[i]=false的点，说明此点对应的强连通已经被缩点过了,而访问的i的起点并不属于这一强连通分量。若这时执行low[x]<br />
= std::min(low[x],dfn[y]);可能会导致一些点在栈内无法弹出。</p>
<p>​<br />
​    #include <cstdio><br />
​    #include <iostream><br />
​    #include <cstring><br />
​    #include <cstdlib><br />
​    #include <algorithm><br />
​    #include <vector><br />
​    #include <map><br />
​    #include <set><br />
​    #include <queue><br />
​    #include <stack><br />
​    typedef long long int LL;<br />
​    //typedef std::pair&lt;int ,int&gt; PP;<br />
​    const int N = 1e4+5, M = 1e5+5;<br />
​    int vis[N],low[N],dfn[N],val[N],head[N],stk[N],suo[N],weight[N],hh[N],in[N],dp[N];<br />
​    struct Edge<br />
​    {<br />
​       int to,nxt;<br />
​    }edg[M&lt;&lt;1];<br />
​    int n,m,u,v;<br />
​    int idx,timer,top,id,tt;<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​       edg[idx].to  = to;<br />
​       edg[idx].nxt = head[fr];<br />
​       head[fr] = idx++;<br />
​    }<br />
​    void tarjin(int x)<br />
​    {<br />
​       low[x] = dfn[x] = <ins>timer;<br />
​       stk[<ins>top] = x,vis[x] = 1;<br />
​       for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
​          int y = edg[e].to;<br />
​          if(!dfn[y]){<br />
​             tarjin(y);<br />
​             low[x] = std::min(low[x],low[y]);<br />
​          }<br />
​          else if(vis[y]){<br />
​             low[x] = std::min(low[x],dfn[y]);<br />
​          }<br />
​       }<br />
​       if(low[x] == dfn[x]){<br />
​          id += 1;<br />
​          while(true){<br />
​             vis[stk[top]] = 0;<br />
​             suo[stk[top]] = id;<br />
​             weight[id] += val[stk[top]];<br />
​             if(x == stk[top–]) break;<br />
​          }<br />
​       }<br />
​    }<br />
​    void rebuild()<br />
​    {<br />
​       for(int i=1; i&lt;=n; i</ins>){<br />
​          for(int e=head[i]; e!=-1; e=edg[e].nxt){<br />
​             int y  = edg[e].to;<br />
​             int ii = suo[i],yy = suo[y];<br />
​             if(ii != yy){<br />
​                in[yy] += 1;<br />
​                edg[idx].to = yy;<br />
​                edg[idx].nxt = hh[ii];<br />
​                hh[ii] = idx</ins>;<br />
​             }<br />
​          }<br />
​       }<br />
​    }<br />
​    int tpsort()<br />
​    {<br />
​       std::queue<int> q;<br />
​       for(int i=1; i&lt;=id; i++){<br />
​          if(!in[i]){<br />
​             q.push(i);<br />
​             dp[i] = weight[i];<br />
​          }<br />
​       }<br />
​       while(!q.empty()){<br />
​          int cur = q.front(); q.pop();<br />
​          for(int e=hh[cur]; e!=-1; e=edg[e].nxt){<br />
​             int  to = edg[e].to;<br />
​             dp[to] = std::max(dp[to],dp[cur]+weight[to]);<br />
​             in[to] -= 1;<br />
​             if(!in[to]) q.push(to);<br />
​          }<br />
​       }<br />
​       int ans = 0;<br />
​       for(int i=1; i&lt;=id; i++){<br />
​          ans = std::max(ans,dp[i]);<br />
​       }<br />
​       return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​       memset(head,-1,sizeof(head));<br />
​       memset(hh,-1,sizeof(hh));<br />
​       scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​       for(int i=1; i&lt;=n; i++){<br />
​          scanf(&quot;%d&quot;,&amp;val[i]);<br />
​       }<br />
​       for(int i=0; i&lt;m; i++){<br />
​          scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​          addEdge(u,v);<br />
​       }<br />
​       for(int i=1; i&lt;=n; i++){<br />
​          if(!dfn[i]) tarjin(i);<br />
​       }<br />
​       rebuild();<br />
​       printf(&quot;%d&quot;,tpsort());<br />
​<br />
return 0;<br />
}</p>
<h2 id="洛谷p3388割点模板"><a class="markdownIt-Anchor" href="#洛谷p3388割点模板"></a> 洛谷P3388割点模板</h2>
<p>trajin中的形参意义为（此点，上一个点），最好改为（此点，过来的边），在做caocao‘s bridge的时候暴露了一些问题</p>
<p>​<br />
​    #include <cstdio><br />
​    #include <iostream><br />
​    #include <cstring><br />
​    #include <cstdlib><br />
​    #include <algorithm><br />
​    #include <vector><br />
​    #include <map><br />
​    #include <set><br />
​    #include <queue><br />
​    #include <stack><br />
​    typedef long long int LL;<br />
​    const int N = 2e4+5, M = 2e5+5;<br />
​    int n,m,u,v;<br />
​    int ans;<br />
​    int idx,timer;<br />
​    int head[N];<br />
​    int low[N],dfn[N],flag[N];<br />
​    struct Edge<br />
​    {<br />
​       int to,nxt;<br />
​    }edg[M];<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​       edg[idx].to = to;<br />
​       edg[idx].nxt = head[fr];<br />
​       head[fr] = idx++;<br />
​    }<br />
​    void tarjin(int x,int fa)<br />
​    {<br />
​       low[x] = dfn[x] = <ins>timer;<br />
​       int son = 0;<br />
​       for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
​          int to = edg[e].to;<br />
​          if(!dfn[to]){<br />
​             son += 1;<br />
​             tarjin(to,x);<br />
​             low[x] = std::min(low[x],low[to]);<br />
​             if(fa &amp;&amp; dfn[x] &lt;= low[to] &amp;&amp; !flag[x]){<br />
​                flag[x] = 1;<br />
​                ans += 1;<br />
​             }<br />
​          }<br />
​          else if(to != fa)low[x] = std::min(low[x],dfn[to]);<br />
​       }<br />
​       if(!fa &amp;&amp; son&gt;=2 &amp;&amp; !flag[x]){<br />
​          flag[x] = 1;<br />
​          ans += 1;<br />
​       }<br />
​    }<br />
​    int main()<br />
​    {<br />
​       //freopen(“D:\EdgeDownloadPlace\P3388_4.in”,“r”,stdin);<br />
​       memset(head,-1,sizeof(head));<br />
​       scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​       for(int i=0; i&lt;m; i</ins>){<br />
​          scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​          addEdge(u,v); addEdge(v,u);<br />
​       }<br />
​       for(int i=1; i&lt;=n; i++){<br />
​         tarjin(i,0);<br />
​       }<br />
​       printf(&quot;%d\n&quot;,ans);<br />
​       for(int i=1; i&lt;=n; i++){<code>在这里插入代码片</code><br />
​          if(flag[i]) printf(&quot;%d &quot;,i);<br />
​       }<br />
​       return 0;<br />
​    }</p>
<h2 id="hdu4738-caocaobridge"><a class="markdownIt-Anchor" href="#hdu4738-caocaobridge"></a> HDU4738 caocao’bridge</h2>
<p>坑点：</p>
<ol>
<li>你需要判断图是否是全部联通的，若不是输出0</li>
<li>若需要派出0个人，则要输出1，至少需要1人才能炸桥</li>
</ol>
<p>——————<br />
最开始在tarjin记录（此点，上一个点），一直wa，猜测可能是有重边，改为记录（此点，过来的边）ac。懒得动脑以后再想。</p>
<p>​<br />
​    #include <cstdio><br />
​    #include <iostream><br />
​    #include <cstring><br />
​    #include <cstdlib><br />
​    #include <algorithm><br />
​    #include <vector><br />
​    #include <map><br />
​    #include <set><br />
​    #include <queue><br />
​    #include <stack><br />
​    typedef long long int LL;<br />
​    const int N = 1005, M = 1000005,INF = 1e6;<br />
​    int n,m,u,v,p;<br />
​    int ans;<br />
​    int head[N],low[N],dfn[N],pp[M];<br />
​    int idx,timer;<br />
​    struct Edge<br />
​    {<br />
​       int to,nxt,p;<br />
​    }edg[M];<br />
​    void addEdge(int u,int v,int p)<br />
​    {<br />
​       edg[idx].to = v;<br />
​       edg[idx].nxt = head[u];<br />
​       edg[idx].p = p;<br />
​       head[u] = idx++;<br />
​    }<br />
​    void initial()<br />
​    {<br />
​       idx = timer = 0;<br />
​       ans = INF;<br />
​       memset(head,-1,sizeof(head));<br />
​       memset(low,0,sizeof(low));<br />
​       memset(dfn,0,sizeof(dfn));<br />
​       memset(pp,0,sizeof(pp));<br />
​    }<br />
​    void tarjin(int x,int bri)<br />
​    {<br />
​       low[x] = dfn[x] = <ins>timer;<br />
​       for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
​          if((e^1) == bri) continue;<br />
​          int y = edg[e].to;<br />
​          if(!dfn[y]){<br />
​             tarjin(y,e);<br />
​             low[x] = std::min(low[x],low[y]);<br />
​             if(dfn[x] &lt; low[y]) pp[e] = pp[e^1] = 1;<br />
​          }<br />
​          else low[x] = std::min(low[x],dfn[y]);<br />
​       }<br />
​    }<br />
​    int main()<br />
​    {<br />
​       while(scanf(&quot;%d%d&quot;,&amp;n,&amp;m)){<br />
​          if(n == 0 &amp;&amp; m == 0) break;<br />
​          initial();<br />
​          for(int i=0; i&lt;m; i</ins>){<br />
​             scanf(&quot;%d%d%d&quot;,&amp;u,&amp;v,&amp;p);<br />
​             addEdge(u,v,p); addEdge(v,u,p);<br />
​          }<br />
​          tarjin(1,-1);<br />
​          bool judge = false;<br />
​          for(int i=1; i&lt;=n; i++){<br />
​             if(!dfn[i]){<br />
​                judge = true;<br />
​                break;<br />
​             }<br />
​          }<br />
​          if(judge) printf(“0\n”);<br />
​          else{<br />
​             for(int e=0; e&lt;idx; e++){<br />
​                if(pp[e] == 1) ans = std::min(ans,edg[e].p);<br />
​             }<br />
​             if(!ans) ans += 1;<br />
​             else if(ans == INF) ans = -1;<br />
​             printf(&quot;%d\n&quot;,ans);<br />
​          }<br />
​       }<br />
​       return 0;<br />
​    }</p>
<p>​</p>
<h2 id="洛谷p2341-usaco03fallhaoi2006受欢迎的牛-g"><a class="markdownIt-Anchor" href="#洛谷p2341-usaco03fallhaoi2006受欢迎的牛-g"></a> 洛谷P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstring><br />
​    #include <string><br />
​    #include <cstdlib><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <stack><br />
​    #include <vector><br />
​    #include <set><br />
​    #include <map><br />
​    typedef long long int LL;<br />
​    typedef std::pair&lt;int ,int&gt; PP;<br />
​    const int N = 1e4, M = 5e4+5, INF = 0x7fffffff;<br />
​    int n,m,u,v,su,sv,cnt;<br />
​    int idx,timer,counter;<br />
​    int head[N],low[N],dfn[N],vis[N],suo[N],num[N],out[N];<br />
​    PP qry[M];<br />
​    std::stack<int> stk;<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt;<br />
​    }edg[M];<br />
​    void initial()<br />
​    {<br />
​        idx = 2;<br />
​    }<br />
​    void addEdge(int fr,int to)<br />
​    {<br />
​        edg[idx].to =to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    void tarjin(int x)<br />
​    {<br />
​        dfn[x] = low[x] = <ins>timer;<br />
​        vis[x] = true;<br />
​        stk.push(x);<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            int y = edg[e].to;<br />
​            if(!dfn[y]){<br />
​                tarjin(y);<br />
​                low[x] = std::min(low[x],low[y]);<br />
​            }<br />
​            else if(vis[y]) low[x] = std::min(low[x],dfn[y]);<br />
​        }<br />
​        if(low[x] == dfn[x]){<br />
​            counter += 1;<br />
​            while(true){<br />
​                int t = stk.top(); stk.pop();<br />
​                suo[t] = counter;<br />
​                num[counter] += 1;<br />
​                vis[t] = false;<br />
​                if(t == x) break;<br />
​            }<br />
​        }<br />
​    }<br />
​    int main()<br />
​    {<br />
​        initial();<br />
​        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);<br />
​        for(int i=0; i&lt;m; i</ins>){<br />
​            scanf(&quot;%d%d&quot;,&amp;qry[i].first,&amp;qry[i].second);<br />
​            addEdge(qry[i].first,qry[i].second);<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) if(!dfn[i]) tarjin(i);<br />
​        for(int i=0; i&lt;m; i++){<br />
​            u = qry[i].first , v = qry[i].second;<br />
​            su = suo[u] , sv = suo[v];<br />
​            if(su == sv) continue;<br />
​            out[su] += 1;<br />
​        }<br />
​        for(int i=1; i&lt;=counter; i++){<br />
​            if(!out[i]){<br />
​                cnt += 1;<br />
​                u = i;<br />
​                if(cnt &gt; 1) break;<br />
​            }<br />
​        }<br />
​        if(cnt == 1) printf(&quot;%d&quot;,num[u]);<br />
​        else printf(“0”);<br />
​        return 0;<br />
​    }</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90tarjin%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0%20%E7%BC%A9%E7%82%B9%EF%BC%8C%E5%89%B2%E7%82%B9%EF%BC%8C%E5%89%B2%E8%BE%B9%E3%80%91%E6%B4%9B%E8%B0%B7_P3387%E7%BC%A9%E7%82%B9%E6%A8%A1%E6%9D%BFP3388%E5%89%B2%E7%82%B9%E6%A8%A1%E6%9D%BF%20HDU4738%20caocao%E2%80%98bridge/" data-id="cl2uhoec3001de4j35mac0qw0" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/tarjin/" rel="tag">tarjin</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%89%B2%E7%82%B9/" rel="tag">割点</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%89%B2%E8%BE%B9/" rel="tag">割边</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BC%A9%E7%82%B9/" rel="tag">缩点</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【二分图匹配 练习】洛谷P3386【模板】二分图最大匹配P2756飞行员配对方案问题P1129矩阵游戏P1559运动员最佳匹配问题P4014分配问题P1640连续攻击游戏" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E4%BA%8C%E5%88%86%E5%9B%BE%E5%8C%B9%E9%85%8D%20%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P3386%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E4%BA%8C%E5%88%86%E5%9B%BE%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8DP2756%E9%A3%9E%E8%A1%8C%E5%91%98%E9%85%8D%E5%AF%B9%E6%96%B9%E6%A1%88%E9%97%AE%E9%A2%98P1129%E7%9F%A9%E9%98%B5%E6%B8%B8%E6%88%8FP1559%E8%BF%90%E5%8A%A8%E5%91%98%E6%9C%80%E4%BD%B3%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98P4014%E5%88%86%E9%85%8D%E9%97%AE%E9%A2%98P1640%E8%BF%9E%E7%BB%AD%E6%94%BB%E5%87%BB%E6%B8%B8%E6%88%8F/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E4%BA%8C%E5%88%86%E5%9B%BE%E5%8C%B9%E9%85%8D%20%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P3386%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E4%BA%8C%E5%88%86%E5%9B%BE%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8DP2756%E9%A3%9E%E8%A1%8C%E5%91%98%E9%85%8D%E5%AF%B9%E6%96%B9%E6%A1%88%E9%97%AE%E9%A2%98P1129%E7%9F%A9%E9%98%B5%E6%B8%B8%E6%88%8FP1559%E8%BF%90%E5%8A%A8%E5%91%98%E6%9C%80%E4%BD%B3%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98P4014%E5%88%86%E9%85%8D%E9%97%AE%E9%A2%98P1640%E8%BF%9E%E7%BB%AD%E6%94%BB%E5%87%BB%E6%B8%B8%E6%88%8F/">【二分图匹配 练习】洛谷P3386【模板】二分图最大匹配P2756飞行员配对方案问题P1129矩阵游戏P1559运动员最佳匹配问题P4014分配问题P1640连续攻击游戏.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3386模板二分图最大匹配"><a class="markdownIt-Anchor" href="#洛谷-p3386模板二分图最大匹配"></a> 洛谷 P3386【模板】二分图最大匹配</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 505;<br />
​    int mp[N][N],link[N],vis[N];<br />
​    int n,m,e,u,v,ans;<br />
​    bool dfs(int x)<br />
​    {<br />
​        for(int i=1; i&lt;=m; i++){<br />
​            if(!vis[i] &amp;&amp; mp[x][i]){<br />
​                vis[i] = 1;<br />
​                if(!link[i] || dfs(link[i])){<br />
​                    link[i] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;e);<br />
​        for(int i=0; i&lt;e; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;u,&amp;v);<br />
​            mp[u][v] = 1;<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++) {<br />
​            memset(vis,0,sizeof(vis));<br />
​            ans += dfs(i);<br />
​        }<br />
​        printf(&quot;%d&quot;,ans);<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p2756飞行员配对方案问题"><a class="markdownIt-Anchor" href="#洛谷-p2756飞行员配对方案问题"></a> 洛谷 P2756飞行员配对方案问题</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 105;<br />
​    int mp[N][N],vis[N],link[N];<br />
​    int n,m,u,v,ans;<br />
​    bool dfs(int x)<br />
​    {<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(!vis[i] &amp;&amp; mp[x][i]){<br />
​                vis[i] = 1;<br />
​                if(!link[i] || dfs(link[i])){<br />
​                    link[i] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        scanf(&quot;%d%d&quot;,&amp;m,&amp;n);<br />
​        n-=m;<br />
​        while(scanf(&quot;%d%d&quot;,&amp;u,&amp;v)){<br />
​            if(u == -1 &amp;&amp; v == -1) break;<br />
​            mp[u][v-m] = 1;<br />
​        }<br />
​        for(int i=1; i&lt;=m; i++) {<br />
​            memset(vis,0,sizeof(vis));<br />
​            ans += dfs(i);<br />
​        }<br />
​        printf(&quot;%d\n&quot;,ans);<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(link[i]) printf(&quot;%d %d\n&quot;,link[i],i+m);<br />
​        }<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p1129-zjoi2007-矩阵游戏"><a class="markdownIt-Anchor" href="#洛谷-p1129-zjoi2007-矩阵游戏"></a> 洛谷 P1129 [ZJOI2007] 矩阵游戏</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 205;<br />
​    int mp[N][N],vis[N],link[N];<br />
​    int t,n,ans;<br />
​    bool dfs(int x)<br />
​    {<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(!vis[i] &amp;&amp; mp[x][i]){<br />
​                vis[i] = 1;<br />
​                if(!link[i] || dfs(link[i])){<br />
​                    link[i] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        scanf(&quot;%d&quot;,&amp;t);<br />
​        while(t–){<br />
​            memset(link,0,sizeof(link));<br />
​            ans = 0;<br />
​            scanf(&quot;%d&quot;,&amp;n);<br />
​            for(int i=1; i&lt;=n; i++){<br />
​                for(int j=1; j&lt;=n; j++){<br />
​                    scanf(&quot;%d&quot;,&amp;mp[i][j]);<br />
​                }<br />
​            }<br />
​            for(int i=1; i&lt;=n; i++){<br />
​                memset(vis,0,sizeof(vis));<br />
​                ans += dfs(i);<br />
​            }<br />
​            printf(ans == n ? “Yes\n” : “No\n”);<br />
​        }<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷p1559-运动员最佳匹配问题"><a class="markdownIt-Anchor" href="#洛谷p1559-运动员最佳匹配问题"></a> 洛谷P1559 运动员最佳匹配问题</h2>
<p>两种敲代码方法，一种dfs完算tmp，一种在dfs中算tmp。不确定是否一种比另一种更优，这道题后者时间占优，然而下一道题 <strong>洛谷 P4014<br />
分配问题</strong> 前者时间占优。</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 205,INF = 0x7fffffff;<br />
​    int mp[N][N],lx[N],ly[N],visx[N],visy[N],link[N];<br />
​    int n,tmp,v;<br />
​    bool dfs(int x)<br />
​    {<br />
​        visx[x] = 1;<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(!visy[i] &amp;&amp; lx[x]+ly[i]==mp[x][i]){<br />
​                visy[i] = 1;<br />
​                if(!link[i] || dfs(link[i])){<br />
​                    link[i] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int one()<br />
​    {<br />
​        int ans = 0;<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            lx[i] = std::max(lx[i],mp[i][j]);<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            while(true){<br />
​                memset(visx,0,sizeof(visx));<br />
​                memset(visy,0,sizeof(visy));<br />
​                tmp = INF;<br />
​                if(dfs(i)) break;<br />
​                for(int i=1; i&lt;=n; i++) if(visx[i]){<br />
​                    for(int j=1; j&lt;=n; j++) if(!visy[j]){<br />
​                        tmp = std::min(tmp,lx[i]+ly[j]-mp[i][j]);<br />
​                    }<br />
​                }<br />
​                for(int j=1; j&lt;=n; j++){<br />
​                    if(visx[j]) lx[j] -= tmp;<br />
​                    if(visy[j]) ly[j] += tmp;<br />
​                }<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            ans += ly[i] + lx[link[i]];<br />
​            //std::cout &lt;&lt; “ly[” &lt;&lt; i &lt;&lt; “] = &quot; &lt;&lt; ly[i] &lt;&lt; &quot; lx[” &lt;&lt; link[i] &lt;&lt; “] = &quot; &lt;&lt; lx[link[i]] &lt;&lt; &quot; ans = &quot; &lt;&lt; ans &lt;&lt; std::endl;<br />
​        }<br />
​        return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        //freopen(“D:\EdgeDownloadPlace\P4014_1.in”,“r”,stdin);<br />
​        scanf(”%d&quot;,&amp;n);<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            scanf(&quot;%d&quot;,&amp;v);<br />
​            mp[i][j] = -v;<br />
​        }<br />
​        for(int i=0; i&lt;N; i++) lx[i] = -INF;<br />
​        printf(&quot;%d\n&quot;,-one());<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            mp[i][j] = -mp[i][j];<br />
​        }<br />
​        memset(lx,0,sizeof(lx));<br />
​        memset(ly,0,sizeof(ly));<br />
​        memset(link,0,sizeof(link));<br />
​        printf(&quot;%d\n&quot;,one());<br />
​        return 0;<br />
​    }</p>
<p>​<br />
​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int N = 23,INF = 0x7fffffff;<br />
​    int mp[N][N],vm[N],vf[N],vism[N],visf[N],link[N];<br />
​    int n,v,ans,tmp;<br />
​    bool dfs(int x)<br />
​    {<br />
​        vism[x] = 1;<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(!visf[i]){<br />
​                int t = vm[x]+vf[i]-mp[x][i];<br />
​                if(t==0){<br />
​                    visf[i] = 1;<br />
​                    if(!link[i] || dfs(link[i])){<br />
​                        link[i] = x;<br />
​                        return true;<br />
​                    }<br />
​<br />
}<br />
else if(t&gt;0){<br />
tmp = std::min(t,tmp);<br />
}<br />
}<br />
}<br />
return false;<br />
}<br />
int main()<br />
{<br />
scanf(&quot;%d&quot;,&amp;n);<br />
for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++) {<br />
scanf(&quot;%d&quot;,&amp;mp[i][j]);<br />
}<br />
for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++) {<br />
scanf(&quot;%d&quot;,&amp;v);<br />
mp[j][i] *= v;<br />
}<br />
for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++) {<br />
vm[i] = std::max(vm[i],mp[i][j]);<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
while(true){<br />
memset(visf,0,sizeof(visf));<br />
memset(vism,0,sizeof(vism));<br />
tmp = INF;<br />
if(dfs(i))break;<br />
for(int i=1; i&lt;=n; i++){<br />
if(visf[i]) vf[i] += tmp;<br />
if(vism[i]) vm[i] -= tmp;<br />
}<br />
}<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
ans += vf[i] + vm[link[i]];<br />
}<br />
printf(&quot;%d&quot;,ans);<br />
return 0;<br />
}</p>
<h2 id="洛谷-p4014-分配问题"><a class="markdownIt-Anchor" href="#洛谷-p4014-分配问题"></a> 洛谷 P4014 分配问题</h2>
<p><s>全WA，我的输出莫名其妙出现了&quot;-&quot;，洛谷判题机的锅？</s><br />
破案了，one()里的ans没初始化，Windows自动给个0，Linux就挂了，初始化成0就好了</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <algorithm><br />
​    #include <queue><br />
​    #include <map><br />
​    #include <stack><br />
​    #include <string><br />
​    #include <cstring><br />
​    #include <vector><br />
​    #include <cmath><br />
​    #include <set>	<br />
​    typedef long long int LL;<br />
​    const int N = 105,INF = 0x7fffffff;<br />
​    int mp[N][N],lx[N],ly[N],visx[N],visy[N],link[N];<br />
​    int n,tmp,v;<br />
​    bool dfs(int x)<br />
​    {<br />
​        visx[x] = 1;<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(!visy[i] &amp;&amp; lx[x]+ly[i]==mp[x][i]){<br />
​                visy[i] = 1;<br />
​                if(!link[i] || dfs(link[i])){<br />
​                    link[i] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int one()<br />
​    {<br />
​        int ans;<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            lx[i] = std::max(lx[i],mp[i][j]);<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            while(true){<br />
​                memset(visx,0,sizeof(visx));<br />
​                memset(visy,0,sizeof(visy));<br />
​                tmp = INF;<br />
​                if(dfs(i)) break;<br />
​                for(int i=1; i&lt;=n; i++){<br />
​                    if(visx[i]){<br />
​                        for(int j=1; j&lt;=n; j++){<br />
​                            if(!visy[j]){<br />
​                                tmp = std::min(tmp,lx[i]+ly[j]-mp[i][j]);<br />
​                            }<br />
​                        }<br />
​                    }<br />
​                }<br />
​                for(int j=1; j&lt;=n; j++){<br />
​                    if(visx[j]) lx[j] -= tmp;<br />
​                    if(visy[j]) ly[j] += tmp;<br />
​                }<br />
​            }<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            ans += ly[i] + lx[link[i]];<br />
​        }<br />
​        return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        //freopen(“D:\EdgeDownloadPlace\P4014_1.in”,“r”,stdin);<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            scanf(&quot;%d&quot;,&amp;v);<br />
​            mp[i][j] = -v;<br />
​        }<br />
​        for(int i=0; i&lt;N; i++) lx[i] = -INF;<br />
​        printf(&quot;%d\n&quot;,-one());<br />
​        for(int i=1; i&lt;=n; i++) for(int j=1; j&lt;=n; j++){<br />
​            mp[i][j] = -mp[i][j];<br />
​        }<br />
​        memset(lx,0,sizeof(lx));<br />
​        memset(ly,0,sizeof(ly));<br />
​        memset(link,0,sizeof(link));<br />
​        printf(&quot;%d\n&quot;,one());<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p1640连续攻击游戏"><a class="markdownIt-Anchor" href="#洛谷-p1640连续攻击游戏"></a> 洛谷 P1640连续攻击游戏</h2>
<p>匈牙利优化 每次memset置零vis数组太慢了，TLE，直接开一个变量timmer当作时间计数，当timmer-<br />
vis[x]&gt;0就说明在这次dfs中x节点没有访问过。<br />
.<br />
初始timmer为1， 每次dfs后timmer自增1</p>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int INF = 0x7fffffff, SCF = 0x3fffffff;<br />
​    const int N = 1e6+5, M = 220, K = 1e6+4;<br />
​    int head[N],link[N],vis[N];<br />
​    int n,idx,a,b,timmer;<br />
​    struct Edge<br />
​    {<br />
​        int to,nxt;<br />
​    }edg[N&lt;&lt;1];<br />
​    void addE(int fr,int to)<br />
​    {<br />
​        edg[idx].to = to;<br />
​        edg[idx].nxt = head[fr];<br />
​        head[fr] = idx++;<br />
​    }<br />
​    bool dfs(int x)<br />
​    {<br />
​        for(int e=head[x]; e; e=edg[e].nxt){<br />
​            int y = edg[e].to;<br />
​            if(timmer-vis[y]&gt;0){<br />
​                vis[y] = timmer;<br />
​                if(!link[y] || dfs(link[y])){<br />
​                    link[y] = x;<br />
​                    return true;<br />
​                }<br />
​            }<br />
​        }<br />
​        return false;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        idx = 2;<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            scanf(&quot;%d%d&quot;,&amp;a,&amp;b);<br />
​            addE(a,i);<br />
​            addE(b,i);<br />
​        }<br />
​        int i;<br />
​        for(i=1; i&lt;=n; i++){<br />
​            timmer = i;<br />
​            if(!dfs(i)) break;<br />
​        }<br />
​        printf(&quot;%d&quot;,i-1);<br />
​        return 0;<br />
​    }</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E4%BA%8C%E5%88%86%E5%9B%BE%E5%8C%B9%E9%85%8D%20%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P3386%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E4%BA%8C%E5%88%86%E5%9B%BE%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8DP2756%E9%A3%9E%E8%A1%8C%E5%91%98%E9%85%8D%E5%AF%B9%E6%96%B9%E6%A1%88%E9%97%AE%E9%A2%98P1129%E7%9F%A9%E9%98%B5%E6%B8%B8%E6%88%8FP1559%E8%BF%90%E5%8A%A8%E5%91%98%E6%9C%80%E4%BD%B3%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98P4014%E5%88%86%E9%85%8D%E9%97%AE%E9%A2%98P1640%E8%BF%9E%E7%BB%AD%E6%94%BB%E5%87%BB%E6%B8%B8%E6%88%8F/" data-id="cl2uhoec4001ge4j32azj2roz" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/KM%E7%AE%97%E6%B3%95/" rel="tag">KM算法</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E4%BA%8C%E5%88%86%E5%9B%BE/" rel="tag">二分图</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" rel="tag">匈牙利算法</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【二叉树】 给出二叉树的中序遍历 和先序遍历或后序遍历 确定二叉树" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%91%20%E7%BB%99%E5%87%BA%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%20%E5%92%8C%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86%E6%88%96%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%20%E7%A1%AE%E5%AE%9A%E4%BA%8C%E5%8F%89%E6%A0%91/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%91%20%E7%BB%99%E5%87%BA%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%20%E5%92%8C%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86%E6%88%96%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%20%E7%A1%AE%E5%AE%9A%E4%BA%8C%E5%8F%89%E6%A0%91/">【二叉树】 给出二叉树的中序遍历 和先序遍历或后序遍历 确定二叉树.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p><strong>讨论的内容如题</strong></p>
<h2 id="分析"><a class="markdownIt-Anchor" href="#分析"></a> 分析</h2>
<p>拿中序遍历和后序遍历的组合举例子<br />
设数组last[]储存后续遍历 in[]中序遍历，它们的长度都是n(数组从1开始计，下标范围是1-n)</p>
<p>树根自然为last[n]<br />
，这时我们遍历in[]数组，在in[]数组中找到last[n]的值的下标idx，因为in[]储存的是中序遍历，显然我们以idx为界把in数组的序列分成两份[1,idx-1],[idx+1,n]，分别为两颗子树上的节点。</p>
<p>之后我们便可以在分出的两个区间之中重复上述操作，分别找目前子树的根节点，再二分区间，直到获得完整的二叉树</p>
<p>可以使用递归来完成 函数(区间左，区间右，根节点，偏移量)</p>
<p>此时注意一个问题：当区间被二分之后，我们发现后面的区间在in[]数组和last[]数组中的下标“对不齐”了，即下标发生了偏移，如下图。所以要引入一个变量shift来记录偏移量。（偏移量最开始是0，递归时前面的区间继承原偏移量，后面的区间偏移量为原偏移量+1）<br />
![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20201008231828150.png?x-oss-">https://img-blog.csdnimg.cn/20201008231828150.png?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)<br />
（在前序遍历和中序遍历的组合中，下标发生偏移的是前面的区间）</p>
<h2 id="例题-后序遍历和中序遍历的组合"><a class="markdownIt-Anchor" href="#例题-后序遍历和中序遍历的组合"></a> 例题 后序遍历和中序遍历的组合</h2>
<p><a target="_blank" rel="noopener" href="https://vjudge.net/contest/386054#problem/E">https://vjudge.net/contest/386054#problem/E</a></p>
<p>​<br />
#include <iostream><br />
#include <cstring><br />
#include <cstdio><br />
struct Node<br />
{<br />
int l,r;<br />
};<br />
Node treeN[10010];<br />
int inorder[10010],postorder[10010];<br />
int len,rt,least,lstPos;<br />
int input()//返回数组长度<br />
{<br />
int n,idx=1;<br />
char ch;<br />
while(scanf(&quot;%d&quot;,&amp;n)!=EOF)<br />
{<br />
inorder[idx++]=n;<br />
ch=getchar();<br />
if(ch==’\n’)<br />
break;<br />
}<br />
idx=1;<br />
while(scanf(&quot;%d&quot;,&amp;n)!=EOF)<br />
{<br />
postorder[idx++]=n;<br />
ch=getchar();<br />
if(ch==’\n’)<br />
break;<br />
}<br />
return idx-1;<br />
}<br />
int makeTree(int l,int r,int root,int n)<br />
{<br />
if(l&gt;r)<br />
return -1;<br />
int idx=-1;<br />
for(int i=l; i&lt;=r; i++)<br />
{<br />
if(inorder[i]<mark>root)<br />
{<br />
idx=i;<br />
break;<br />
}<br />
}<br />
if(idx&gt;0)<br />
{<br />
treeN[root].l=makeTree(l,idx-1,postorder[idx-n-1],n);<br />
treeN[root].r=makeTree(idx+1,r,postorder[r-n-1],n+1);<br />
}<br />
return root;<br />
}<br />
void add(int root,int base)<br />
{<br />
int total=base+root;<br />
if(treeN[root].l</mark>-1 &amp;&amp; treeN[root].r==-1)<br />
{<br />
if(lstPos==-1)<br />
{<br />
least=total;<br />
lstPos=root;<br />
}<br />
else<br />
{<br />
if(total&lt;least)<br />
{<br />
least=total;<br />
lstPos=root;<br />
}<br />
}<br />
return ;<br />
}<br />
if(treeN[root].l&gt;0)<br />
{<br />
add(treeN[root].l,total);<br />
}<br />
if(treeN[root].r&gt;0)<br />
{<br />
add(treeN[root].r,total);<br />
}<br />
}</p>
<pre><code>int main()
&#123;
    while((len=input())&gt;0)
    &#123;
        memset(treeN,-1,sizeof(treeN));
        lstPos=-1;
        rt=makeTree(1,len,postorder[len],0);
        add(rt,0);
        std::cout &lt;&lt; lstPos &lt;&lt; std::endl;
    &#125;
    return 0;
&#125;
</code></pre>
<p>​</p>
<h2 id="例题-前序遍历和中序遍历的组合"><a class="markdownIt-Anchor" href="#例题-前序遍历和中序遍历的组合"></a> 例题 前序遍历和中序遍历的组合</h2>
<p>&lt;<a target="_blank" rel="noopener" href="https://pintia.cn/problem-">https://pintia.cn/problem-</a><br />
sets/1303281293857476608/problems/1303281404742291466&gt;</p>
<p>​<br />
#include <iostream><br />
#include <cstdio><br />
#include <cstring><br />
#include <algorithm><br />
#include <iomanip><br />
#include <queue><br />
#include <cmath><br />
#include <map></p>
<pre><code>const int N=32;
int n;
struct Node
&#123;
    int l,r;
&#125;treeN[N];
int pre[N],in[N];

int fff(int root,int l,int r,int shift)
&#123;
    if(l&gt;r) return -1;
    int i;
    for(i=l; i&lt;=r; i++) if(root==in[i]) break;
    if(i&lt;=r)
    &#123;
        treeN[root].l=fff(pre[l+1+shift],l,i-1,shift+1);
        treeN[root].r=fff(pre[i+1+shift],i+1,r,shift);
    &#125;
    return root;
&#125;

void rev(int root)
&#123;
    if(root==0) return ;
    treeN[root].r=treeN[root].r^treeN[root].l;
    treeN[root].l=treeN[root].r^treeN[root].l;
    treeN[root].r=treeN[root].r^treeN[root].l;
    rev(treeN[root].l);
    rev(treeN[root].r);
&#125;

void gogogo(int root)
&#123;
    std::queue&lt;int &gt;q;
    std::cout &lt;&lt; root;
    if(treeN[root].l!=-1) q.push(treeN[root].l);
    if(treeN[root].r!=-1) q.push(treeN[root].r);
    while(!q.empty())
    &#123;
        root=q.front(); q.pop();
        std::cout &lt;&lt; &quot; &quot; &lt;&lt; root;
        if(treeN[root].l!=-1) q.push(treeN[root].l);
        if(treeN[root].r!=-1) q.push(treeN[root].r);
    &#125;
&#125;

int main()
&#123;
    std::cin &gt;&gt; n;
    for(int i=0; i&lt;n; i++) std::cin &gt;&gt; in[i];
    for(int i=0; i&lt;n; i++) std::cin &gt;&gt; pre[i];
    int root=fff(pre[0],0,n-1,0);
    rev(root);
    gogogo(root);
    return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%91%20%E7%BB%99%E5%87%BA%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%20%E5%92%8C%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86%E6%88%96%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%20%E7%A1%AE%E5%AE%9A%E4%BA%8C%E5%8F%89%E6%A0%91/" data-id="cl2uhoec5001he4j3b82yaqjo" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DFS/" rel="tag">DFS</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DFS%E5%BA%8F/" rel="tag">DFS序</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【单源最短路 spfa Dijkstra】 _ 洛谷 P3371 【模板】单源最短路径（弱化版）_ ## lguou" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%20spfa%20Dijkstra%E3%80%91%20_%20%E6%B4%9B%E8%B0%B7%20P3371%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%EF%BC%88%E5%BC%B1%E5%8C%96%E7%89%88%EF%BC%89_%20##%20lguou/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%20spfa%20Dijkstra%E3%80%91%20_%20%E6%B4%9B%E8%B0%B7%20P3371%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%EF%BC%88%E5%BC%B1%E5%8C%96%E7%89%88%EF%BC%89_%20##%20lguou/">【单源最短路 spfa Dijkstra】 _ 洛谷 P3371 【模板】单源最短路径（弱化版）_</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3371-模板单源最短路径弱化版"><a class="markdownIt-Anchor" href="#洛谷-p3371-模板单源最短路径弱化版"></a> 洛谷 P3371 【模板】单源最短路径（弱化版）</h2>
<p>Dijkstra</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <cstdlib><br />
#include <algorithm><br />
#include <vector><br />
#include <map><br />
#include <set><br />
#include <queue><br />
#include <stack><br />
typedef long long int LL;<br />
const int N = 1e4+5, M = 5e5+5,INF = 0x7fffffff;<br />
int n,m,u,v,d,s;<br />
int idx;<br />
int head[N],dis[N];<br />
bool vis[N];<br />
struct Edge<br />
{<br />
int to,nxt,d;<br />
}edg[M];<br />
void addEdge(int fr,int to,int d)<br />
{<br />
edg[idx].to = to;<br />
edg[idx].nxt = head[fr];<br />
edg[idx].d = d;<br />
head[fr] = idx++;<br />
}<br />
struct PPP<br />
{<br />
int val,dis;<br />
bool operator &lt; (const PPP &amp;x) const{<br />
return dis &gt; x.dis;<br />
}<br />
};<br />
std::priority_queue<PPP> q;<br />
int main()<br />
{<br />
//freopen(“D:\EdgeDownloadPlace\P3371_2.in”,“r”,stdin);<br />
memset(head,-1,sizeof(head));<br />
for(int i=0;i&lt;N; i++) dis[i] = INF;<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
for(int i=1; i&lt;=m; i++){<br />
scanf(&quot;%d%d%d&quot;,&amp;u,&amp;v,&amp;d);<br />
addEdge(u,v,d);<br />
}<br />
dis[s] = 0;<br />
q.push((PPP){s,0});<br />
while(!q.empty()){<br />
PPP cur = q.top(); q.pop();<br />
int x = cur.val;<br />
if(vis[x]) continue;<br />
vis[x] = true;<br />
for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
int y = edg[e].to;<br />
if(dis[y] &gt; dis[x]+edg[e].d){<br />
dis[y] = dis[x]+edg[e].d;<br />
q.push((PPP){y,dis[y]});<br />
}<br />
}<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
printf(&quot;%d &quot;,dis[i]);<br />
}<br />
return 0;<br />
}</p>
<p>spfa(个人感觉就是纯bfs)</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <cstdlib><br />
#include <algorithm><br />
#include <vector><br />
#include <map><br />
#include <set><br />
#include <queue><br />
#include <stack><br />
typedef long long int LL;<br />
const int N = 1e4+5, M = 5e5+5,INF = 0x7fffffff;<br />
int dis[N],head[N];<br />
bool vis[N];<br />
int n,m,u,v,d,s;<br />
int idx;<br />
struct Edge<br />
{<br />
int to,nxt,d;<br />
}edg[M];<br />
void addEdge(int fr,int to,int d)<br />
{<br />
edg[idx].to = to;<br />
edg[idx].nxt = head[fr];<br />
edg[idx].d = d;<br />
head[fr] = idx++;<br />
}<br />
std::queue<int> q;<br />
int main()<br />
{<br />
memset(head,-1,sizeof(head));<br />
memset(vis,0,sizeof(vis));<br />
for(int i=0; i&lt;N; i++) dis[i] = INF;<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
for(int i=0; i&lt;m; i++){<br />
scanf(&quot;%d%d%d&quot;,&amp;u,&amp;v,&amp;d);<br />
addEdge(u,v,d);<br />
}<br />
dis[s] = 0;<br />
q.push(s);<br />
while(!q.empty()){<br />
int x = q.front(); q.pop(); vis[x] = false;<br />
for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
int y = edg[e].to;<br />
if(dis[y] &gt; dis[x]+edg[e].d){<br />
dis[y] = dis[x]+edg[e].d;<br />
if(!vis[y]){<br />
vis[y] = true;<br />
q.push(y);<br />
}<br />
}<br />
}<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
printf(&quot;%d &quot;,dis[i]);<br />
}<br />
return 0;<br />
}</p>
<h2 id="洛谷p4779-模板单源最短路径标准版"><a class="markdownIt-Anchor" href="#洛谷p4779-模板单源最短路径标准版"></a> 洛谷P4779 【模板】单源最短路径（标准版）</h2>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <cstdlib><br />
#include <algorithm><br />
#include <vector><br />
#include <map><br />
#include <set><br />
#include <queue><br />
#include <stack><br />
typedef long long int LL;<br />
const int N = 1e5+5, M = 2e5+5,INF = 0x7fffffff;<br />
int n,m,u,v,d,s;<br />
int idx;<br />
int head[N],dis[N];<br />
bool vis[N];<br />
struct Edge<br />
{<br />
int to,nxt,d;<br />
}edg[M];<br />
void addEdge(int fr,int to,int d)<br />
{<br />
edg[idx].to = to;<br />
edg[idx].nxt = head[fr];<br />
edg[idx].d = d;<br />
head[fr] = idx++;<br />
}<br />
struct PPP<br />
{<br />
int val,dis;<br />
bool operator &lt; (const PPP &amp;x) const{<br />
return dis &gt; x.dis;<br />
}<br />
};<br />
std::priority_queue<PPP> q;<br />
int main()<br />
{<br />
//freopen(“D:\EdgeDownloadPlace\P3371_2.in”,“r”,stdin);<br />
memset(head,-1,sizeof(head));<br />
for(int i=0;i&lt;N; i++) dis[i] = INF;<br />
scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;s);<br />
for(int i=1; i&lt;=m; i++){<br />
scanf(&quot;%d%d%d&quot;,&amp;u,&amp;v,&amp;d);<br />
addEdge(u,v,d);<br />
}<br />
dis[s] = 0;<br />
q.push((PPP){s,0});<br />
while(!q.empty()){<br />
PPP cur = q.top(); q.pop();<br />
int x = cur.val;<br />
if(vis[x]) continue;<br />
vis[x] = true;<br />
for(int e=head[x]; e!=-1; e=edg[e].nxt){<br />
int y = edg[e].to;<br />
if(dis[y] &gt; dis[x]+edg[e].d){<br />
dis[y] = dis[x]+edg[e].d;<br />
q.push((PPP){y,dis[y]});<br />
}<br />
}<br />
}<br />
for(int i=1; i&lt;=n; i++){<br />
printf(&quot;%d &quot;,dis[i]);<br />
}<br />
return 0;<br />
}</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%20spfa%20Dijkstra%E3%80%91%20_%20%E6%B4%9B%E8%B0%B7%20P3371%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%EF%BC%88%E5%BC%B1%E5%8C%96%E7%89%88%EF%BC%89_%20##%20lguou/" data-id="cl2uhoec6001ke4j31de3h7qn" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/BFS/" rel="tag">BFS</a></li></ul>

    </footer>
  </div>
  
</article>




  


  <nav id="page-nav">
    <a class="extend prev" rel="prev" href="/page/2/">&lt;&lt;&lt; 上一页</a><a class="page-number" href="/">1</a><a class="page-number" href="/page/2/">2</a><span class="page-number current">3</span><a class="page-number" href="/page/4/">4</a><a class="page-number" href="/page/5/">5</a><span class="space">&hellip;</span><a class="page-number" href="/page/8/">8</a><a class="extend next" rel="next" href="/page/4/">下一页 &gt;&gt;&gt;</a>
  </nav>
</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>